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

2
00:00:11,100 --> 00:00:12,300
>> Ræðumaður 1: Hey allir!

3
00:00:12,300 --> 00:00:13,890
Velkomin aftur til kafla.

4
00:00:13,890 --> 00:00:17,480
Svo fegin að sjá svo mörg ykkar bæði hér,
og hver sem er að horfa á netinu.

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

6
00:00:18,760 --> 00:00:20,920
Svo, eins og venjulega velkominn.

7
00:00:20,920 --> 00:00:24,360
Ég vona að þú hefðir allt yndisleg
helgi, fullur af hvíld, slökun.

8
00:00:24,360 --> 00:00:26,026
Það var falleg í gær.

9
00:00:26,026 --> 00:00:27,525
Svo ég vona að þú njóta utandyra.

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

11
00:00:28,840 --> 00:00:30,610
>> Svo fyrst par tilkynninga.

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

13
00:00:31,920 --> 00:00:32,700
Flokkun.

14
00:00:32,700 --> 00:00:37,350
Svo, flest ykkar ættu að hafa fengið að
email frá mér um Scratch Pset þína,

15
00:00:37,350 --> 00:00:39,920
sem og fyrir flokkun á Pset 1.

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

17
00:00:41,000 --> 00:00:42,220
Svo, bara nokkra hluti.

18
00:00:42,220 --> 00:00:45,150
Vertu viss um að nota check50 í style50.

19
00:00:45,150 --> 00:00:47,250
Þetta er ætlað að vera
úrræði fyrir ykkur,

20
00:00:47,250 --> 00:00:50,660
að ganga úr skugga um að þú ert að fá
eins mörg stig eins og þú getur

21
00:00:50,660 --> 00:00:52,390
án óþörfu tapa þeim.

22
00:00:52,390 --> 00:00:54,407
Svo hlutir eins stíl
eru mjög mikilvæg.

23
00:00:54,407 --> 00:00:55,740
Við erum að fara að taka burt fyrir það.

24
00:00:55,740 --> 00:00:58,115
Sumir af þú mega hafa þegar
tók eftir því að frá Pset þínum.

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

26
00:00:58,920 --> 00:01:01,450
Og check50 er bara
mjög auðveld leið til að ganga úr skugga um

27
00:01:01,450 --> 00:01:05,050
að við erum í raun að aftur hvað
þarf að koma aftur til the notandi,

28
00:01:05,050 --> 00:01:06,690
og að allt er að vinna almennilega.

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

30
00:01:08,690 --> 00:01:12,040
>> Á annarri huga, tryggja þinn
hlaða það til the réttur mappa.

31
00:01:12,040 --> 00:01:14,470
Það gerir líf mitt bara
svolítið erfiðara

32
00:01:14,470 --> 00:01:18,836
ef þú sendir Pset 2 inná Pset 1
vegna þess að þegar ég sótt hlutina,

33
00:01:18,836 --> 00:01:20,085
þeir sæki ekki rétt.

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

35
00:01:21,690 --> 00:01:24,560
Og ég veit að það er lítið wonky
í kerfi að venjast,

36
00:01:24,560 --> 00:01:26,950
en bara vera frábær
varkár, ef aðeins fyrir mig,

37
00:01:26,950 --> 00:01:30,080
þannig að þegar þú ert að fá tölvupóst
á eins 02:00 og ég er einkunnakerfi.

38
00:01:30,080 --> 00:01:33,710
Ef ekki því ég verð að líta
allt í kring um Pset þína.

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

40
00:01:34,440 --> 00:01:37,270
>> Ég veit að það er snemma, en ég
algerlega fékk tekið burt vörður

41
00:01:37,270 --> 00:01:40,800
með ritgerð sem er vegna á föstudaginn, þann
prófessorar mínir voru bara eins, ó já.

42
00:01:40,800 --> 00:01:42,550
Mundu, þú hefur
ritgerð vegna á föstudaginn.

43
00:01:42,550 --> 00:01:45,780
Svo, ég veit enginn finnst
að hugsa um midterms,

44
00:01:45,780 --> 00:01:50,620
en fyrst quiz er 15. október,
sem október er að hefjast í þessari viku.

45
00:01:50,620 --> 00:01:53,290
Svo það gæti verið fyrr
en búist er allur.

46
00:01:53,290 --> 00:01:57,510
Svo að þú ert ekki kastað burt vörður þegar
Ég nefni næstu viku kafla sem ó,

47
00:01:57,510 --> 00:02:00,560
quiz næstu viku þinn, hugsaði ég
Ég myndi gefa þér smá meira

48
00:02:00,560 --> 00:02:01,500
af a höfuð núna.

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

50
00:02:02,970 --> 00:02:04,660
>> Svo, vandamál þitt sett, númer þrjú.

51
00:02:04,660 --> 00:02:07,070
Hvernig fólk hefur lesið
sérstakur út af forvitni?

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
Við fengum nokkra.

55
00:02:10,229 --> 00:02:12,320
Konar niður frá síðustu
viku en það er allt í lagi.

56
00:02:12,320 --> 00:02:13,650
Ég veit að það var fallegt út.

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

58
00:02:15,120 --> 00:02:16,660
Svo brjótast út.

59
00:02:16,660 --> 00:02:21,010
Ákveðið eftir að þú fá gert
dag lesa sérstakur amk

60
00:02:21,010 --> 00:02:25,240
reyna eins sækja
dreifingu kóða og keyra

61
00:02:25,240 --> 00:02:27,430
eins og fyrsta upphaflega
hlutur sem þeir biðja um.

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

63
00:02:28,681 --> 00:02:32,590
Vegna þess að við erum að nota
dreifingu kóða og bókasafn

64
00:02:32,590 --> 00:02:36,790
að við höfum aðeins verið að using-- --It er bara
í annað skipti sem við höfum gert þetta Pset,

65
00:02:36,790 --> 00:02:38,650
brjálaður hlutir geta gerst
með tækið þitt,

66
00:02:38,650 --> 00:02:41,370
og þú vilt að finna að
út núna á móti síðar.

67
00:02:41,370 --> 00:02:45,570
>> Vegna þess að ef það er fimmtudagskvöld eða það er
Miðvikudagskvöldið og fyrir sumir ástæða

68
00:02:45,570 --> 00:02:48,912
Búnaðurinn er bara ekki
langar að hlaupa með á bókasafnið

69
00:02:48,912 --> 00:02:50,620
eða með dreifingu
númer, sem þýðir

70
00:02:50,620 --> 00:02:52,309
þú getur ekki einu sinni byrjað að gera erfðaskrá.

71
00:02:52,309 --> 00:02:54,100
Þar sem þú getur ekki stöðva
til að sjá hvort það virkar.

72
00:02:54,100 --> 00:02:55,975
Ekki ađ þitt vera fær
til að sjá hvort það safnar.

73
00:02:55,975 --> 00:03:00,500
Þú vilt að gæta af þeim snemma í
viku, þegar þú getur samt email mig

74
00:03:00,500 --> 00:03:03,100
eða einn af hinum TFS,
og við getum fengið þá fastur.

75
00:03:03,100 --> 00:03:05,410
Vegna þess að þeir eru málefni
sem eru að fara að stoppa þig

76
00:03:05,410 --> 00:03:07,120
frá því allir alvöru framfarir.

77
00:03:07,120 --> 00:03:10,055
Það er ekki eins og einn galla, að
þú getur bara svona sleppa yfir.

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

79
00:03:10,712 --> 00:03:13,420
Ef þú ert að hafa mál með þinn
tæki eða dreifingu kóða,

80
00:03:13,420 --> 00:03:16,211
þú vilt virkilega að fá að taka
umönnun fyrr frekar en síðar.

81
00:03:16,211 --> 00:03:20,410
Svo jafnvel ef þú ert ekki ađ raun
byrja kóðun, sækja dreifingu

82
00:03:20,410 --> 00:03:24,040
kóða, lesa sérstakur, ganga úr skugga um
allt er að vinna þar.

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

84
00:03:25,134 --> 00:03:27,675
Ef þú getur bara gert það, ég
lofa líf þitt verður auðveldara.

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

86
00:03:28,800 --> 00:03:31,410
Og svo þú ert líklega að fara
að gera það núna ekki satt?

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

88
00:03:32,100 --> 00:03:33,950
Svo, einhverjar spurningar þarna?

89
00:03:33,950 --> 00:03:35,850
Allar logistic hlutir?

90
00:03:35,850 --> 00:03:36,910
Allir er gott?

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

92
00:03:38,270 --> 00:03:41,700
>> Fyrirvari fyrir þau
þú í herberginu og á netinu.

93
00:03:41,700 --> 00:03:45,437
Ég ætla að vera að reyna að skipta
milli PowerPoint í tækið

94
00:03:45,437 --> 00:03:47,270
vegna þess að við erum að fara
að vera að gera einhverja kóðun

95
00:03:47,270 --> 00:03:53,630
dag með eftirspurnar af nafnlaus
tillaga kosning Ég sendi út í síðustu viku.

96
00:03:53,630 --> 00:03:55,480
Svo munum við vera að gera sumir kóðun.

97
00:03:55,480 --> 00:03:57,800
Svo ef þú krakkar vilja einnig
að skjóta upp tæki þínum,

98
00:03:57,800 --> 00:04:02,910
og þú ættir að hafa fengið tölvupóst
frá mér, með sýnishorn skrá.

99
00:04:02,910 --> 00:04:04,310
Vinsamlegast ekki hika við að gera það.

100
00:04:04,310 --> 00:04:07,340
>> Svo erum við að fara að tala um
GDB, sem er aflúsara.

101
00:04:07,340 --> 00:04:09,970
Það er að fara að hjálpa þér
konar reikna út hvar

102
00:04:09,970 --> 00:04:11,860
hlutirnir eru að fara úrskeiðis í kóðanum þínum.

103
00:04:11,860 --> 00:04:15,370
Það er í raun bara leið fyrir þig til að stíga
gegnum númerið þitt eins og það er að gerast,

104
00:04:15,370 --> 00:04:19,100
og vera fær um að prenta út breytur
eða sjá hvað er raunverulega að gerast

105
00:04:19,100 --> 00:04:22,980
undir hetta vers program
bara að keyra, það er eins faulting,

106
00:04:22,980 --> 00:04:25,030
og þú ert eins og, ekki hugmynd
hvað bara gerðist hér.

107
00:04:25,030 --> 00:04:26,730
Ég veit ekki hvað lína það ekki á.

108
00:04:26,730 --> 00:04:29,040
Ég veit ekki hvar það fór úrskeiðis.

109
00:04:29,040 --> 00:04:31,280
Svo, GDB er að fara að hjálpa þér með það.

110
00:04:31,280 --> 00:04:35,240
Einnig, ef þú ákveður að
áfram já, og taka 61,

111
00:04:35,240 --> 00:04:38,430
það mun í raun, í raun að vera þitt
besti vinur, því ég get sagt þér

112
00:04:38,430 --> 00:04:40,840
vegna þess að ég ætla að fara í gegnum þeim flokki.

113
00:04:40,840 --> 00:04:43,620
>> Við erum að fara að horfa á tvöfaldur
leita, sem ef þú krakkar muna

114
00:04:43,620 --> 00:04:47,540
mikill símaskránni dæmi
sjón af bekknum.

115
00:04:47,540 --> 00:04:50,620
Við munum vera að innleiða það, og
ganga í gegnum það svolítið meira,

116
00:04:50,620 --> 00:04:54,650
og þá erum við að fara í gegnum fjögur
mismunandi tegundir, sem eru Bubble,

117
00:04:54,650 --> 00:04:56,285
Val, innsetningu, og sameinast.

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
Svo, GDB eins og ég nefndi, er aflúsara.

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

122
00:05:01,400 --> 00:05:09,370
Og þetta eru eins konar stór
hluti, stóru aðgerðir eða skipanir

123
00:05:09,370 --> 00:05:13,240
sem þú notar innan gdb, og ég mun ganga
þú gegnum kynningu um það í sekúndu.

124
00:05:13,240 --> 00:05:15,360
>> Svo, þetta er ekki bara
fara að vera ágrip.

125
00:05:15,360 --> 00:05:18,000
Ég ætla að reyna og gera það sem steypu
og mögulegt er fyrir ykkur.

126
00:05:18,000 --> 00:05:19,870
Svo, brjóta.

127
00:05:19,870 --> 00:05:22,200
Það verður annað hvort að vera brjóta
eins, sumir tala, sem

128
00:05:22,200 --> 00:05:26,900
táknar línu í forritinu,
eða þú getur kallað aðgerð.

129
00:05:26,900 --> 00:05:30,150
Svo, ef þú segir brjóta helstu,
það hættir á helstu,

130
00:05:30,150 --> 00:05:32,400
og láta þig ganga í gegnum þessi virka.

131
00:05:32,400 --> 00:05:36,350
>> Sömuleiðis, ef þú hafa sumir utanaðkomandi
virka eins Víxla eða Cube,

132
00:05:36,350 --> 00:05:38,450
að við skoðuðum í síðustu viku.

133
00:05:38,450 --> 00:05:41,780
Ef þú segir brýtur eitt af þeim,
hvenær program hits að

134
00:05:41,780 --> 00:05:44,290
það mun bíða eftir þér að
segja það hvað ég á að gera.

135
00:05:44,290 --> 00:05:47,860
Áður en það verður bara að framkvæma þannig að þú
gæti raunverulega stíga inn í aðgerð

136
00:05:47,860 --> 00:05:49,020
og sjá hvað er að gerast.

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

138
00:05:50,370 --> 00:05:53,515
Svo, Next, bara sleppa yfir
næsta lína, fer yfir aðgerðir.

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
Þetta eru allar litlu ágrip.

142
00:05:56,810 --> 00:06:00,530
Svo ég ætla bara að fara að hlaupa í gegnum þá,
en þú munt sjá þá í notkun í annarri.

143
00:06:00,530 --> 00:06:01,810
>> Stíga inn í aðgerð.

144
00:06:01,810 --> 00:06:04,170
Svo eins og ég var að segja,
eins og með Víxla, myndi það

145
00:06:04,170 --> 00:06:07,110
leyfa þú til raunverulega eins og ef þú ert
eins líkamlega stepping inni,

146
00:06:07,110 --> 00:06:10,990
þú getur klúðrar með þeim breytum, prenta
hvað þeir eru, sjá hvað er að gerast.

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

148
00:06:12,140 --> 00:06:14,830
Listi mun bókstaflega bara prenta
út umhverfis kóða.

149
00:06:14,830 --> 00:06:17,570
Svo ef þú gleymir konar
hvar þú ert í forritinu,

150
00:06:17,570 --> 00:06:19,880
eða þú ert að velta fyrir mér
hvað er að gerast í kringum það,

151
00:06:19,880 --> 00:06:23,790
þetta mun bara prenta út hluti
af eins og fimm eða sex línur í kringum hana.

152
00:06:23,790 --> 00:06:26,080
Svo er hægt að fá stilla
um hvar þú ert.

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

154
00:06:27,230 --> 00:06:28,650
>> Prenta sumir breytu.

155
00:06:28,650 --> 00:06:34,590
Svo ef þú hefur lykillinn eins
í keisaranum sem við munum líta á.

156
00:06:34,590 --> 00:06:36,220
Þú getur sagt Prenta takkann á hverjum tímapunkti.

157
00:06:36,220 --> 00:06:40,070
Það mun segja þér hvaða gildi er svo
að kannski einhvers staðar á leiðinni,

158
00:06:40,070 --> 00:06:42,070
þú overwrote lykil.

159
00:06:42,070 --> 00:06:45,495
Þú getur í raun sagt að vegna þess að
þú getur raunverulega sjá að gildi.

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

161
00:06:46,500 --> 00:06:48,780
>> Í heimamenn, bara framköllun
út staðbundnar breytur þínar.

162
00:06:48,780 --> 00:06:53,120
Svo, hvenær þú ert innan lykkju
og þú vilt bara til að sjá eins og ó.

163
00:06:53,120 --> 00:06:54,270
Hvað er ég mitt?

164
00:06:54,270 --> 00:06:57,020
Hvað er þetta lykill gildi
að ég frumstilla hér?

165
00:06:57,020 --> 00:06:58,537
Hver er boðskapurinn á þessum tímapunkti?

166
00:06:58,537 --> 00:07:00,370
Það verður bara að prenta allt
af þeim, svo að þér

167
00:07:00,370 --> 00:07:04,330
þarft ekki að sig
segja, Print I. Print Message.

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
Og þá sýna.

171
00:07:07,700 --> 00:07:10,370
Hvað það gerir er eins og þú
stíga í gegnum forritið,

172
00:07:10,370 --> 00:07:13,980
Það verður bara að ganga úr skugga um að það er
sýna einhverja ákveðna breytu

173
00:07:13,980 --> 00:07:14,780
á hverjum stað.

174
00:07:14,780 --> 00:07:17,160
Svo að þú also-- --it er
konar smákaka þar

175
00:07:17,160 --> 00:07:19,530
þú þarft ekki að halda áfram eins og, ó.

176
00:07:19,530 --> 00:07:23,150
Print Key eða Print I. Það bara
mun sjálfkrafa gera það fyrir þig.

177
00:07:23,150 --> 00:07:25,959
>> Svo, með það, við erum að fara
til að sjá hvernig þetta fer.

178
00:07:25,959 --> 00:07:28,000
Ég ætla að reyna og skipta
yfir til tæki minn.

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

180
00:07:30,200 --> 00:07:31,271
Sjá hvort ég get gert þetta.

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

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

183
00:07:40,970 --> 00:07:42,370
Við erum bara að fara að spegla það.

184
00:07:42,370 --> 00:07:44,530
Það er ekkert brjálaður
á minn laptop engu að síður.

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
Þetta þarf að vera svona einn.

189
00:08:01,054 --> 00:08:01,795
Það er svo lítið.

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

191
00:08:03,730 --> 00:08:05,120
Við skulum sjá hvort við getum gert þetta.

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 er augljóslega erfiðleikum
hér bara svolítið,

195
00:08:15,305 --> 00:08:17,995
en við munum fá þ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
Við erum bara að fara að auka þetta.

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
Geta allir konar sjá að?

202
00:08:31,679 --> 00:08:32,470
Kannski svolítið?

203
00:08:32,470 --> 00:08:33,594
Ég veit að það er svolítið lítil.

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

205
00:08:34,570 --> 00:08:37,530
Þú getur ekki alveg reikna út
hvernig á að gera þetta stærra.

206
00:08:37,530 --> 00:08:38,350
Ef einhver veit.

207
00:08:38,350 --> 00:08:40,309
Hefur einhver veit hvernig á að gera það stærri?

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

209
00:08:40,932 --> 00:08:42,140
Við erum að fara að rúlla með það.

210
00:08:42,140 --> 00:08:45,801
Skiptir ekki máli hvort eð því það er bara
það er kóðinn sem þú krakkar ættu

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

212
00:08:46,300 --> 00:08:48,310
>> Hvað er mikilvægara
er flugstöðinni hér.

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

214
00:08:52,840 --> 00:08:58,690
Og við höfum hér Hvers vegna er það svo lítið?

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

216
00:09:02,325 --> 00:09:02,825
Stillingar.

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
True Ike.

220
00:09:09,500 --> 00:09:10,880
Hvernig er þetta?

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

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

223
00:09:19,370 --> 00:09:21,810
Er það betra fyrir alla?

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
>> Þú veist þegar þú ert í CS
flokki tæknilegir erfiðleikar

228
00:09:28,220 --> 00:09:32,971
eru eins konar hluti af the--
Svo skulum við hreinsa þetta.

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

230
00:09:33,470 --> 00:09:38,060
Svo, hérna í kafla,
sem við höfðum hér.

231
00:09:38,060 --> 00:09:40,830
Caesar er executable skrá.

232
00:09:40,830 --> 00:09:41,800
Svo ég gerði það.

233
00:09:41,800 --> 00:09:46,370
Svo eitt að átta sig með GDB er
að það virkar aðeins á executable skrá.

234
00:09:46,370 --> 00:09:48,040
Svo getur þú ekki keyrt hana á dotsy.

235
00:09:48,040 --> 00:09:50,532
Þú þarft að raunverulega gera
viss um að kóðinn þinn safnar,

236
00:09:50,532 --> 00:09:51,865
og að það getur í raun að keyra.

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

238
00:09:52,970 --> 00:09:56,186
>> Svo, ganga úr skugga um að ef það virkar ekki
saman, fá það til að safna saman,

239
00:09:56,186 --> 00:09:57,810
þannig að þú getur konar hlaupa í gegnum það.

240
00:09:57,810 --> 00:10:04,590
Svo, til að byrja GDB, allt sem þú gerir,
Gloria tegund GDB, og þá bara

241
00:10:04,590 --> 00:10:06,250
skrá sem þú vilt.

242
00:10:06,250 --> 00:10:08,240
Ég stafa vitlaust alltaf Caesar.

243
00:10:08,240 --> 00:10:11,730
En þú vilt ganga úr skugga um
þar sem það er óákveðinn greinir í ensku executable,

244
00:10:11,730 --> 00:10:14,210
punktur glampi Ti, svo að
þýðir að þú ert að fara

245
00:10:14,210 --> 00:10:19,240
að keyra CSI þú ert að fara að framkvæma
þetta skrá annaðhvort með aflúsara.

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

247
00:10:19,910 --> 00:10:22,885
Svo, þú þarft að þú færð
þessu tagi gibberish.

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

249
00:10:24,250 --> 00:10:25,750
Það er bara allt um aflúsara.

250
00:10:25,750 --> 00:10:28,200
Þú þarft í raun ekki að
hafa áhyggjur af því núna.

251
00:10:28,200 --> 00:10:31,460
Og eins og þú sérð, höfum við á þessu
opna parens landsframleiðslan, loka parens,

252
00:10:31,460 --> 00:10:34,690
og bara svona lítur eins
stjórn lína okkar, ekki satt?

253
00:10:34,690 --> 00:10:37,010
>> Svo, það sem við viljum að do--
--So, Það fyrsta sem

254
00:10:37,010 --> 00:10:39,570
er að við viljum að velja
staður til að brjóta það.

255
00:10:39,570 --> 00:10:42,332
Svo, það er einn padda
í þessu Caesar áætlun

256
00:10:42,332 --> 00:10:44,290
sem ég kynna að
við erum að fara að finna út.

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

258
00:10:45,330 --> 00:10:56,350
Hann það sem hann gerir er að það tekur inntak
Barfoo í öllum húfur, og fyrir sumir ástæða

259
00:10:56,350 --> 00:11:01,950
það breytir ekki A. Það fer bara
það eitt og sér, er allt annað rétt,

260
00:11:01,950 --> 00:11:03,980
en annað bréf
A óbreytt.

261
00:11:03,980 --> 00:11:07,120
Svo erum við að fara að reyna að
reikna út hvers vegna það er.

262
00:11:07,120 --> 00:11:10,440
Svo, the fyrstur hlutur þú venjulega
vilja til að gera þegar þú byrjar á gdb

263
00:11:10,440 --> 00:11:12,010
er að reikna út hvar á að brjóta það.

264
00:11:12,010 --> 00:11:14,956
>> Svo er Caesar ansi stutt program.

265
00:11:14,956 --> 00:11:16,330
Við höfum bara eina aðgerð, ekki satt?

266
00:11:16,330 --> 00:11:18,520
Hvað var virka okkar í keisarans?

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

268
00:11:19,590 --> 00:11:24,350
Það er aðeins ein aðgerð, Main satt?

269
00:11:24,350 --> 00:11:26,490
Main er fall
fyrir öll forrit.

270
00:11:26,490 --> 00:11:29,230
Ef þú myndað af did ekki hafa helstu, gæti ég
vera smá áhyggjur núna,

271
00:11:29,230 --> 00:11:31,000
en ég vona að þú hefðir allt Main þar.

272
00:11:31,000 --> 00:11:34,150
Svo, hvað við getum gert er að við getum
bara brjóta helstu, bara svona.

273
00:11:34,150 --> 00:11:35,190
Svo segir það, OK.

274
00:11:35,190 --> 00:11:37,430
Við setjum breakpoint einn okkar þar.

275
00:11:37,430 --> 00:11:42,870
>> Svo, nú hlutur til muna er Caesar
tekur einn stjórn rök lína rétt

276
00:11:42,870 --> 00:11:45,150
og við höfum ekki gert það einhvers staðar enn.

277
00:11:45,150 --> 00:11:47,560
Svo, hvað þú gerir er þegar
þú ferð í raun að keyra

278
00:11:47,560 --> 00:11:51,540
The program, hvaða forrit sem þú ert
gangi í gdb sem þarf stjórn lína

279
00:11:51,540 --> 00:11:55,010
rök, ert þú að fara að inntak
þegar þú byrjar fyrst að keyra hana.

280
00:11:55,010 --> 00:11:59,280
Svo, í þessu tilfelli, gera við
Hlaupa með lykill af þremur.

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

282
00:12:00,770 --> 00:12:02,040
Og það mun í raun að byrja.

283
00:12:02,040 --> 00:12:08,480
>> Svo ef þú sérð hér, höfum við
Ef RC er ekki jafnt og 2.

284
00:12:08,480 --> 00:12:12,210
Svo ef þú krakkar hafa allir
þessi skrá sem ég sendi út allt

285
00:12:12,210 --> 00:12:15,100
þú munt sjá að það er eins og
Fyrsta lína Meginhlutverk okkar, ekki satt?

286
00:12:15,100 --> 00:12:17,890
Það er að haka við að sjá hvort við höfum
réttan fjölda rök.

287
00:12:17,890 --> 00:12:20,620
Svo, ef þú ert að velta fyrir mér
ef RC er rétt,

288
00:12:20,620 --> 00:12:23,250
þú getur gert eitthvað bara eins Print RC.

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

290
00:12:24,380 --> 00:12:28,640
RC er tveir, sem er
hvað við ráð fyrir, ekki satt?

291
00:12:28,640 --> 00:12:32,010
>> Svo getum við farið á Next,
og halda áfram í gegnum.

292
00:12:32,010 --> 00:12:33,200
Svo höfum við nokkur lykil þar.

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

294
00:12:34,260 --> 00:12:37,090
Og við getum prentað út lykill okkar
til að tryggja það er rétt.

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

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

297
00:12:39,500 --> 00:12:41,210
Ekki alveg það sem við bjuggumst við.

298
00:12:41,210 --> 00:12:44,810
Svo eitt að gera sér grein fyrir
með gdb Einnig er

299
00:12:44,810 --> 00:12:49,000
að það er ekki fyrr en þú högg í raun
Next, að línan sem þú sást bara

300
00:12:49,000 --> 00:12:50,720
er í raun framkvæmt.

301
00:12:50,720 --> 00:12:53,870
Svo, í þessu tilfelli Key
hefur ekki verið úthlutað ennþá.

302
00:12:53,870 --> 00:12:57,050
Svo, Key er sumir sorp gildi
sem þú sérð á the botn þar.

303
00:12:57,050 --> 00:13:03,680
Neikvætt $ 120-- --It er einn milljarð
og eitthvað stakur hlutina rétt?

304
00:13:03,680 --> 00:13:05,340
Það er ekki lykillinn sem við bjuggumst við.

305
00:13:05,340 --> 00:13:10,720
En ef við högg á Next og þá erum við
reyna Print takkann, er það þrisvar.

306
00:13:10,720 --> 00:13:11,710
>> Allir sjá að?

307
00:13:11,710 --> 00:13:13,780
Svo ef þú færð eitthvað
að þú ert eins og, bíddu.

308
00:13:13,780 --> 00:13:15,540
Þetta er alveg
rangt, og ég veit ekki

309
00:13:15,540 --> 00:13:20,150
hvernig þetta myndi gerast því allt sem ég vil
að gera er að tengja símanúmer, breytu,

310
00:13:20,150 --> 00:13:22,900
reyna hitting Next, reyna prentun
það aftur og sjá hvort það virkar.

311
00:13:22,900 --> 00:13:27,830
Því það er bara að fara að framkvæma og
reyndar framselja eitthvað eftir yður

312
00:13:27,830 --> 00:13:29,340
högg á Next.

313
00:13:29,340 --> 00:13:30,336
Skynsamleg fyrir alla?

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

315
00:13:30,836 --> 00:13:33,220
>> Ræðumaður 2: Þegar þú handahófi
tölur hvað þýðir það?

316
00:13:33,220 --> 00:13:34,790
>> Ræðumaður 1: Það er bara af handahófi.

317
00:13:34,790 --> 00:13:35,710
Það er bara sorp.

318
00:13:35,710 --> 00:13:38,320
Það er bara eitthvað sem þinn
tölvan mun handahófi úthluta.

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
Svo nú getum við fara í gegnum, og svo
nú höfum við þetta látlaus texta GetString.

322
00:13:45,760 --> 00:13:48,600
Svo láta mig kynna bara hvað
mun gerast þegar við högg Next hér.

323
00:13:48,600 --> 00:13:51,320
GDB okkar konar hverfur, ekki satt?

324
00:13:51,320 --> 00:13:55,720
Það er vegna þess að GetString
er nú framkvæmd, ekki satt?

325
00:13:55,720 --> 00:14:01,460
Svo, þegar við sáum texta jafngildir
GetString, opin parens og parens,

326
00:14:01,460 --> 00:14:04,380
og við högg Next, sem hefur
reyndar keyrð núna.

327
00:14:04,380 --> 00:14:06,580
Svo, það er að bíða eftir
okkur að inntak eitthvað.

328
00:14:06,580 --> 00:14:13,560
>> Svo erum við að fara að inntak mat okkar sem
er það sem það er galli sem ég sagði þér

329
00:14:13,560 --> 00:14:18,020
og það bara segir að það er
lokið framkvæmd, að lokað

330
00:14:18,020 --> 00:14:19,980
krappi þýðir að það er
spennandi út úr því lykkja.

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

332
00:14:21,170 --> 00:14:25,420
Svo getum við högg Next, og nú, eins og ég er
viss um að þú ert allur þekki frá keisarans,

333
00:14:25,420 --> 00:14:27,260
þetta er, hvað er þessi lína að fara að gera.

334
00:14:27,260 --> 00:14:32,030
Það er fyrir Int I er 0, N jafngildir
Strlen, texta, og þá

335
00:14:32,030 --> 00:14:33,960
I er minna en n, I, auk, plús.

336
00:14:33,960 --> 00:14:35,210
Hvað er þetta lykkja fara að gera?

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

338
00:14:37,900 --> 00:14:39,160
Opnaðu skilaboðin.

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

340
00:14:39,770 --> 00:14:41,330
Svo, við skulum byrja að gera það.

341
00:14:41,330 --> 00:14:47,210
>> Svo ætti þetta ástand
passa, fyrir fyrsta einn okkar?

342
00:14:47,210 --> 00:14:52,250
Ef það er B, það er látlaus texti I. Við
hægt að fá upplýsingar um heimamenn okkar.

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

344
00:14:53,610 --> 00:14:57,970
Svo, ég er núll, og ef sex, sem
við gerum ráð fyrir, og lykill okkar er þriggja.

345
00:14:57,970 --> 00:14:59,227
Allt sem skynsamleg, ekki satt?

346
00:14:59,227 --> 00:15:01,310
Þær tölur eru allar
nákvæmlega hvað þeir ættu að vera.

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

348
00:15:02,590 --> 00:15:03,870
Svo, raula?

349
00:15:03,870 --> 00:15:05,620
Ræðumaður 3: Ég hef
handahófi tölur fyrir minn.

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

351
00:15:09,156 --> 00:15:12,030
Ræðumaður 1: Jæja, við getum check-- --we
geta spjallað um það í sekúndu.

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

353
00:15:14,110 --> 00:15:15,750
En þú ættir að vera að fá þetta.

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

355
00:15:17,700 --> 00:15:20,130
Svo ef við höfum fjármagn
B fyrir fyrsta okkar,

356
00:15:20,130 --> 00:15:22,080
þetta ástand ætti skilið það, ekki satt?

357
00:15:22,080 --> 00:15:27,120
Svo, ef við högg Next, sjáum við
að þetta Ef keyrir raun.

358
00:15:27,120 --> 00:15:29,220
Vegna þess að ef þú ert að elta
eftir í kóðanum þínum,

359
00:15:29,220 --> 00:15:33,460
þessi lína hér, þar látlaus texti I
er skipt út með þessum tölur,

360
00:15:33,460 --> 00:15:35,720
aðeins framkvæmir ef if
ástand er rétt ekki satt?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB er bara að fara að sýna þér
hlutir sem eru í raun framkvæmd.

363
00:15:40,240 --> 00:15:45,140
Þannig að ef þetta ef ástand var ekki fullnægt, það er
bara að fara til að sleppa í næstu línu.

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

365
00:15:46,540 --> 00:15:48,510
Svo höfum við það.

366
00:15:48,510 --> 00:15:51,171
Þessi krappi þýðir að það er
lokað út af því að lykkja núna.

367
00:15:51,171 --> 00:15:52,420
Svo það er að fara að byrja aftur.

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

369
00:15:54,760 --> 00:15:56,280
Bara svona.

370
00:15:56,280 --> 00:15:59,120
Svo að við getum fengið upplýsingar
um heimamenn okkar hér,

371
00:15:59,120 --> 00:16:02,575
og við sjáum að fyrstu okkar
bréf hefur breyst, ekki satt?

372
00:16:02,575 --> 00:16:05,150
Það er nú E, eins og það ætti að vera.

373
00:16:05,150 --> 00:16:07,360
Svo getum við haldið áfram á.

374
00:16:07,360 --> 00:16:08,500
>> Og við höfum þessa ávísun.

375
00:16:08,500 --> 00:16:09,916
Og þetta stöðva ætti að vinna, ekki satt?

376
00:16:09,916 --> 00:16:12,570
Það er A. Það ætti að breyta
þrír stafir áfram.

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

378
00:16:14,320 --> 00:16:16,530
En ef þú tekur eftir, við
fá eitthvað öðruvísi.

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

380
00:16:17,580 --> 00:16:22,860
Þannig að í þessu tilfelli hér, tók um hann
það, og svo þessi lína keyrð,

381
00:16:22,860 --> 00:16:28,620
sem breytt B. okkar
En, í þessu tilfelli hér,

382
00:16:28,620 --> 00:16:32,860
við höfum það sleppt bara það,
og fór á [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Svo eitthvað er að gerast þar.

384
00:16:34,660 --> 00:16:37,780
Hvað það er að segja þér er að,
við vitum að það ætti skilið hér,

385
00:16:37,780 --> 00:16:39,200
en það er ekki.

386
00:16:39,200 --> 00:16:42,210
Getur einhver séð hvað okkar
Vandamálið er í þeirri línu?

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

388
00:16:45,380 --> 00:16:46,969
Það er mjög mínútu hlutur.

389
00:16:46,969 --> 00:16:48,510
Og þú getur líka að líta á kóðann þinn.

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

391
00:16:49,980 --> 00:16:54,940
Það er líka line-- gleyma hvaða línu það er
í there-- en það er í [inaudible].

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

393
00:16:55,480 --> 00:16:58,639
>> Ræðumaður 4: Það er á meira en
síðu ef þú lest það í bókinni.

394
00:16:58,639 --> 00:16:59,430
Ræðumaður 1: Einmitt.

395
00:16:59,430 --> 00:17:02,620
Svo, aflúsara gat ekki sagt
þú það, en aflúsara

396
00:17:02,620 --> 00:17:05,880
gætu fengið þig niður að línu
að þú veist er ekki að virka.

397
00:17:05,880 --> 00:17:09,319
Og stundum, þegar sérstaklega
síðar í önn, þegar

398
00:17:09,319 --> 00:17:12,910
þú ert að takast á við hundrað, a
hundrað nokkrar línur af kóða, og þú

399
00:17:12,910 --> 00:17:16,190
veit ekki hvar það er galli,
þetta er frábær leið til að gera það.

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

401
00:17:17,900 --> 00:17:18,989
Svo fannst okkur galla okkar.

402
00:17:18,989 --> 00:17:21,530
Þú getur lagað það í skrána,
og þá gætir þú keyrt það aftur,

403
00:17:21,530 --> 00:17:23,029
og allt myndi vinna fullkomlega.

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

405
00:17:24,970 --> 00:17:30,590
Og stærsta málið er
þetta getur virst eins og, OK.

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

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

408
00:17:31,370 --> 00:17:32,744
Þú vissir hvað þú ert að leita að.

409
00:17:32,744 --> 00:17:34,910
Svo, þú vissir hvað ég á að gera.

410
00:17:34,910 --> 00:17:39,021
>> GDB má frábær gagnlegt vegna þess að þú
getur prentað út alla þessa hluti, sem þú

411
00:17:39,021 --> 00:17:39,520
væri ekki.

412
00:17:39,520 --> 00:17:41,160
Það er miklu meira gagni en printf.

413
00:17:41,160 --> 00:17:43,440
Hversu margir af þú notar
eins printf yfirlýsingar

414
00:17:43,440 --> 00:17:46,200
að reikna út hvar villa var, ekki satt?

415
00:17:46,200 --> 00:17:48,450
Svo, með þetta, þú ert ekki
þarf að fara til baka,

416
00:17:48,450 --> 00:17:51,139
og eins athugasemd í
Printf eða athugasemdir út,

417
00:17:51,139 --> 00:17:52,930
og reikna út hvað
þú ættir að vera að prenta.

418
00:17:52,930 --> 00:17:55,670
Þetta í raun bara leyfa þér að
stíga gegnum, prenta út hluti

419
00:17:55,670 --> 00:18:00,000
eins og þú ert að fara í gegnum, svo, þú getur
fylgjast með hvernig þeir breytast í rauntíma,

420
00:18:00,000 --> 00:18:02,190
sem kerfið er í gangi.

421
00:18:02,190 --> 00:18:04,390
>> Og það þýðir að taka smá
hluti af að sættast við.

422
00:18:04,390 --> 00:18:07,850
Ég vildi mjög mæla með bara svona
að vera svolítið svekktur með það

423
00:18:07,850 --> 00:18:08,930
fyrir núna.

424
00:18:08,930 --> 00:18:13,450
Ef þú eyðir klukkutíma yfir
í næstu viku að læra hvernig á að nota GDB,

425
00:18:13,450 --> 00:18:16,140
þú verður að vista sjálfur
svo miklum tíma síðar.

426
00:18:16,140 --> 00:18:18,750
Og bókstaflega. við segja
þetta fólk á hverju ári,

427
00:18:18,750 --> 00:18:23,890
og ég man þegar ég tók
flokki, ég var eins og, Ég mun vera í lagi.

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

429
00:18:24,700 --> 00:18:27,030
Pset 6 kom á og ég var
eins, ég ætla að læra

430
00:18:27,030 --> 00:18:29,500
hvernig á að nota GDB því ég ekki
vita hvað er að gerast hér.

431
00:18:29,500 --> 00:18:32,940
>> Þannig að ef þú takir þér tíma svo
nota það á minni verkefnum

432
00:18:32,940 --> 00:18:35,697
að þú ert að fara til vera
vinna á, eins og að vinna

433
00:18:35,697 --> 00:18:37,530
gegnum eitthvað eins
Visionare, svona.

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

435
00:18:38,800 --> 00:18:42,850
Eða ef þú vilt auka æfa, ég er viss um
Ég gæti komið upp með gallaðir forrit,

436
00:18:42,850 --> 00:18:45,300
fyrir þig að kemba ef þú vilt.

437
00:18:45,300 --> 00:18:49,300
>> En ef þú tekur bara einhvern tíma að fá
venjast því, bara að leika í kring með það,

438
00:18:49,300 --> 00:18:50,550
það verður í raun að þjóna þér vel.

439
00:18:50,550 --> 00:18:52,591
Og það er í raun einn af
Þeir hlutir sem þú bara

440
00:18:52,591 --> 00:18:57,340
verð að reyna, og fá þinn snertið ekki óhrein
með, áður en þú skilur það í raun.

441
00:18:57,340 --> 00:19:02,090
I raun aðeins skilið það einu sinni
Ég þurfti að kemba hluti með það,

442
00:19:02,090 --> 00:19:08,170
og það er miklu betur að hafa hugmynd um
hvernig á að kemba fyrr en síðar.

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
Ég veit það er góður af eins og
a hrun námskeið í GDB,

446
00:19:12,960 --> 00:19:16,400
og ég mun örugglega vinna á getting
þessir að líta stærri næst.

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
>> Svo ef við förum aftur til PowerPoint okkar.

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

451
00:19:27,194 --> 00:19:28,110
Er þetta að fara að vinna?

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
Já.

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

456
00:19:31,600 --> 00:19:35,480
Svo, ef þú alltaf þörf einhverju
þá aftur, það er á listanum.

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

458
00:19:37,160 --> 00:19:40,830
Svo Binary Search, sem allir
minnist mikla sjón Davíðs

459
00:19:40,830 --> 00:19:42,259
stórfínn bækur símann í tvennt.

460
00:19:42,259 --> 00:19:44,050
Ég í raun ekki fá
sími bækur lengur,

461
00:19:44,050 --> 00:19:46,530
vegna eins og hvar heldur þú
fá bækur símann þessa dagana?

462
00:19:46,530 --> 00:19:48,220
Ég virkilega veit ekki.

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

464
00:19:49,840 --> 00:19:50,590
The Binary Search.

465
00:19:50,590 --> 00:19:52,464
Hefur einhver man
hvernig Binary Search virkar?

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

467
00:19:54,380 --> 00:19:55,220
Einhver yfirleitt?

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

469
00:19:56,325 --> 00:19:58,283
Ræðumaður 5: Þú veist þegar
þú horfir á sem helmingur

470
00:19:58,283 --> 00:20:01,146
það væri í, byggist á því,
og losna við hinn helminginn.

471
00:20:01,146 --> 00:20:01,896
>> Ræðumaður 1 Nákvæmlega.

472
00:20:01,896 --> 00:20:06,290
Svo, Binary Search, það er góður af a--
--we kalla það skipta og sigra.

473
00:20:06,290 --> 00:20:09,170
Svo, hvað þú munt gera er
þú munt líta í miðjunni,

474
00:20:09,170 --> 00:20:11,990
og þú munt sjá ef það passar
hvað þú ert að leita að.

475
00:20:11,990 --> 00:20:15,420
Og ef það virkar ekki, þá reyna að
reikna út, er það að fara að vera vinstri

476
00:20:15,420 --> 00:20:16,450
helmingur eða rétt helmingur.

477
00:20:16,450 --> 00:20:19,325
Svo, þetta gæti verið ef þú ert að leita
á eitthvað sem er alphabetized,

478
00:20:19,325 --> 00:20:20,720
þú sérð, ó.

479
00:20:20,720 --> 00:20:22,750
Er Allison koma fyrir M?

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

481
00:20:23,250 --> 00:20:25,030
Svo erum við að fara að
líta á fyrri hluta ársins.

482
00:20:25,030 --> 00:20:26,450
>> Eða það gæti verið eins og með tölum.

483
00:20:26,450 --> 00:20:28,830
Nokkuð sem þú getur
bera saman, það geta vera flokkaður.

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

485
00:20:29,920 --> 00:20:31,260
Þú getur notað tvöfaldur leita á.

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

487
00:20:32,340 --> 00:20:37,455
Svo, einhver man þetta
línurit eða hvað þetta er?

488
00:20:37,455 --> 00:20:39,520
Það er Asymptotic Þyngdarstig.

489
00:20:39,520 --> 00:20:42,830
Svo þetta línurit bara
lýsir hversu lengi það

490
00:20:42,830 --> 00:20:46,230
tekur þig að leysa vandamál eins og
þú aukið fjölda af hlutum

491
00:20:46,230 --> 00:20:47,090
að þú ert að nota.

492
00:20:47,090 --> 00:20:51,260
>> Svo höfum við N, sem er línuleg tími.

493
00:20:51,260 --> 00:20:54,560
Ef N yfir tveimur, sem er lítillega
betri, enn vex frábær fljótur.

494
00:20:54,560 --> 00:20:58,360
Og þá höfum við tenging, sem er
það sem við teljum Tvíundarleit.

495
00:20:58,360 --> 00:21:03,630
Ef við tökum eftir, sem vandamál þitt
fær mikið og miklu stærri,

496
00:21:03,630 --> 00:21:06,600
tíminn sem það tekur þig að leysa það
ekki raunverulega auka það mikið.

497
00:21:06,600 --> 00:21:09,010
Það er eins og sambærileg
hér í upphafi.

498
00:21:09,010 --> 00:21:10,060
Þú ert eins og, OK.

499
00:21:10,060 --> 00:21:13,000
Nokkuð hér er í raun ekki
Sama hvort er notað,

500
00:21:13,000 --> 00:21:16,220
en þú færð út til milljón, milljarð.

501
00:21:16,220 --> 00:21:20,010
Þú ert að reyna að finna some-- --you're
reyna að finna nál í Heysátan.

502
00:21:20,010 --> 00:21:21,550
>> Ég held að þú viljir þetta vandamál.

503
00:21:21,550 --> 00:21:25,850
Þú vilt þetta flókið, ekki
línuleg því fyrir allt sem þú

504
00:21:25,850 --> 00:21:30,049
vita ætla þín vera að leita í gegnum
hver einstaklingur nál, hlutur af heyi,

505
00:21:30,049 --> 00:21:31,340
reyna að leita að nálinni þína.

506
00:21:31,340 --> 00:21:34,730
Og það er ekki of gaman að mínu mati.

507
00:21:34,730 --> 00:21:35,500
Mér líkar hratt.

508
00:21:35,500 --> 00:21:36,620
Ég eins duglegur.

509
00:21:36,620 --> 00:21:40,450
Og eins hardworking nemendur ÞIG
krakkar eru, þú veist vinna betri,

510
00:21:40,450 --> 00:21:43,010
ekki erfiðara tegund hlutur, hvernig þér
getur gert upp þessi reiknirit.

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

512
00:21:45,110 --> 00:21:47,910
>> Svo erum við að fara að ganga
gegnum bara fljótur dæmi.

513
00:21:47,910 --> 00:21:51,090
Ég held að þú krakkar ættu að hafa
a hönd á Binary Search,

514
00:21:51,090 --> 00:21:54,352
en ef einhver er a lítill
loðinn, langar að styrkja það,

515
00:21:54,352 --> 00:21:56,310
við erum að fara að fara bara
gegnum dæmi hér.

516
00:21:56,310 --> 00:21:59,490
Svo, við erum að leita ef
array inniheldur sjö.

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

518
00:22:00,540 --> 00:22:06,010
>> Svo, fyrsta sem við gerum er
líta í miðju, ekki satt?

519
00:22:06,010 --> 00:22:09,340
Og einnig þú ert að fara að vera erfðaskrá
Tvöfaldur Leita í bara annað.

520
00:22:09,340 --> 00:22:11,310
Svo það er að fara að vera skemmtilegt.

521
00:22:11,310 --> 00:22:13,710
Þannig að við að líta í
miðja lítið fylki 3.

522
00:22:13,710 --> 00:22:15,501
Er 3 jafnir 7?

523
00:22:15,501 --> 00:22:16,000
Gerir það ekki.

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

525
00:22:18,670 --> 00:22:19,550
Það er sex.

526
00:22:19,550 --> 00:22:21,480
Svo er það minna en
eða meiri en sjö?

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

528
00:22:23,080 --> 00:22:23,960
Minna en.

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

530
00:22:24,570 --> 00:22:25,170
Nice starf krakkar.

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

532
00:22:25,569 --> 00:22:27,360
Mér finnst ég eins og ég ætti
hafa nammi því ég

533
00:22:27,360 --> 00:22:29,460
langar að kasta út í metra.

534
00:22:29,460 --> 00:22:30,270
Það er það sem ég er að fara að gera í næstu viku.

535
00:22:30,270 --> 00:22:31,436
Það mun halda ykkur skarpur.

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

537
00:22:32,560 --> 00:22:34,690
>> Svo henda við í burtu því
fyrri helmingi, ekki satt?

538
00:22:34,690 --> 00:22:35,670
það var minna en.

539
00:22:35,670 --> 00:22:39,325
við vitum að allt
á þeirri vinstri hönd

540
00:22:39,325 --> 00:22:41,700
er að fara að vera minna en það sem
við erum í raun að leita að.

541
00:22:41,700 --> 00:22:43,491
Svo, það er engin þörf á að
borga eftirtekt til það.

542
00:22:43,491 --> 00:22:45,120
Bara gleyma óður í það.

543
00:22:45,120 --> 00:22:48,720
Svo nú erum við að líta á hægri hönd okkar hlið,
og við skoðum miðjuna þarna,

544
00:22:48,720 --> 00:22:50,510
og nú er það níu.

545
00:22:50,510 --> 00:22:55,510
Svo, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Meiri en það sem við erum
leita að, ekki satt?

547
00:22:57,470 --> 00:22:59,860
Svo erum við að fara að kasta
burt allt til hægri.

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

549
00:23:00,970 --> 00:23:01,940
Eins og þessi.

550
00:23:01,940 --> 00:23:03,700
Nú eru allir sem við vinstri með er einn.

551
00:23:03,700 --> 00:23:07,760
Þannig að við að athuga er þetta eitt, hvað
við erum að leita að? það er.

552
00:23:07,760 --> 00:23:08,970
Við fundum það sem við vildum.

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

554
00:23:10,440 --> 00:23:11,690
Þannig að við erum að gera.

555
00:23:11,690 --> 00:23:12,550
Bilinear Search.

556
00:23:12,550 --> 00:23:15,740
>> Og ef þú tekur eftir, við
átti sjö inntak þar.

557
00:23:15,740 --> 00:23:24,320
Það tók ekki nema okkur eins þrisvar sinnum,
en ef þú ert að gera eins og milljarð,

558
00:23:24,320 --> 00:23:28,190
þú krakkar vita hversu mörg skref það væri
taka ef við hefðum fjóra milljarða hluti?

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

560
00:23:29,940 --> 00:23:30,455
Allar getgátur?

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

562
00:23:32,286 --> 00:23:33,960
Það er 32.

563
00:23:33,960 --> 00:23:37,110
32 Leiðir til að finna eitthvað
í fjóra milljarða

564
00:23:37,110 --> 00:23:39,650
þátturinn array vegna veldi af tveimur.

565
00:23:39,650 --> 00:23:43,550
Svo tvö er að 32, er í fjóra milljarða.

566
00:23:43,550 --> 00:23:50,430
>> Svo falleg brjálaður hvernig þú ert enn innan
eins nokkuð fáeinum skrefum

567
00:23:50,430 --> 00:23:52,650
að finna eitthvað í
fjóra milljarða atriði.

568
00:23:52,650 --> 00:23:55,730
Svo á að huga, við erum
fara að kóða þetta

569
00:23:55,730 --> 00:23:58,950
svo þú krakkar geta raunverulega
konar sjá hvernig þetta virkar.

570
00:23:58,950 --> 00:24:01,520
Allt í lagi, svo þú krakkar geta kóða.

571
00:24:01,520 --> 00:24:04,100
Ég ætla að láta ykkur
tala um smá.

572
00:24:04,100 --> 00:24:07,970
Fá að kynnast fólki í kringum þig, sem er
hvað einhver vildi frá síðasta kafla.

573
00:24:07,970 --> 00:24:10,280
>> Svo fá að vita að fólk í kringum þig.

574
00:24:10,280 --> 00:24:11,305
Tala í smá.

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

576
00:24:12,580 --> 00:24:15,730
Og allt sem ég vil frá þér
krakkar er núna bara

577
00:24:15,730 --> 00:24:17,575
reyna að búa til yfirlit yfir sauðakóða.

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
Whoa.

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

582
00:24:23,320 --> 00:24:29,520
Allt sem ég vil frá ykkur er að þú ert
bara að fara til að fylla í þetta þegar tilfelli.

583
00:24:29,520 --> 00:24:32,170
Þannig að ég hef sett þetta efri
og lægri mörk sem

584
00:24:32,170 --> 00:24:35,250
tákna upphaf
og lok array okkar.

585
00:24:35,250 --> 00:24:40,440
Og þú ert að fara til raunverulega
lykkja í gegnum og reikna út

586
00:24:40,440 --> 00:24:42,470
hvað við erum að gera innan þessa meðan lykkja.

587
00:24:42,470 --> 00:24:45,810
>> Svo ef þú getur fundið out-- ég hef
vísbending there-- hvað eru tilfelli

588
00:24:45,810 --> 00:24:46,640
að við höfum hér?

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

590
00:24:48,100 --> 00:24:51,560
Svo ef þú vilt að reikna út
tilvikum munum við sauðakóða þeim

591
00:24:51,560 --> 00:24:53,350
og þá munum við í raun að kóða þau.

592
00:24:53,350 --> 00:24:55,330
Og það er að fara að vera, ég
hugsa, vonandi það verður

593
00:24:55,330 --> 00:24:56,788
vera svolítið auðveldara en þú átt von á.

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

595
00:24:57,554 --> 00:25:00,220
Vegna þess að það er ekki það mikið kóða,
reyndar, sem er mjög flott.

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
>> Nemandi: [inaudible]?

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

600
00:25:36,984 --> 00:25:37,650
Umsjón: Já.

601
00:25:37,650 --> 00:25:38,595
Það var eitthvað
að finna í miðju.

602
00:25:38,595 --> 00:25:39,552
>> Nemandi: Svo við getum notað það.

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

604
00:25:39,770 --> 00:25:40,603
>> Umsjón: Perfect.

605
00:25:40,603 --> 00:25:42,950
Svo er það fyrsta sem við þurfum að gera.

606
00:25:42,950 --> 00:25:44,330
Svo að finna miðjuna.

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

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

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

610
00:25:47,770 --> 00:25:55,010
Svo þú ert með hugmynd um hvernig við gætum
í raun að finna miðju með kóða?

611
00:25:55,010 --> 00:25:55,980
>> Nemandi: Já.

612
00:25:55,980 --> 00:25:57,000
n yfir 2?

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

614
00:25:58,500 --> 00:25:59,500
Umsjón: So n yfir 2.

615
00:25:59,500 --> 00:26:05,170
Svo er eitt sem þarf að muna að
efri og neðri mörk breytast.

616
00:26:05,170 --> 00:26:08,110
Við höldum að þrengja hluta
í fylkinu við erum að leita að.

617
00:26:08,110 --> 00:26:11,970
Svo n yfir 2 mun aðeins vinna
í fyrsta sem við gerum.

618
00:26:11,970 --> 00:26:17,810
Svo taka efri og neðri mið,
hvernig gætum við fengið að miðju þáttur?

619
00:26:17,810 --> 00:26:20,640
Vegna þess að við viljum að miðju
milli efri og neðri, ekki satt?

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
>> Nemandi: [inaudible].

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

624
00:26:26,170 --> 00:26:28,080
>> Umsjón: Þannig að við höfum sumir miðju.

625
00:26:28,080 --> 00:26:32,730
Og það verður efri plús minni á 2.

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

627
00:26:34,740 --> 00:26:35,690
Ógnvekjandi.

628
00:26:35,690 --> 00:26:36,570
There við förum.

629
00:26:36,570 --> 00:26:37,280
Ein lína niður.

630
00:26:37,280 --> 00:26:38,560
Þú krakkar eru á vegi þínum.

631
00:26:38,560 --> 00:26:41,400
Svo nú er að við höfum okkar
miðja, hvað viljum við gera?

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

633
00:26:45,050 --> 00:26:45,900
Bara almennt.

634
00:26:45,900 --> 00:26:47,734
Þú þarft ekki að kóða það.

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

636
00:26:48,335 --> 00:26:49,210
Nemandi: [inaudible]?

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

638
00:27:00,310 --> 00:27:10,310
Umsjón: Svo það er plús vegna þess að þú ert
finna meðaltal á milli tveggja

639
00:27:10,310 --> 00:27:10,810
af þeim.

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

641
00:27:11,890 --> 00:27:17,370
Svo ef þú hugsa um þá eins konar
auka í frá hliðum,

642
00:27:17,370 --> 00:27:21,640
hugsa um það eins og þú nálgast
miðju, þú vilt svona.

643
00:27:21,640 --> 00:27:27,150
Svo ef þú varst á hvorri hlið af the
miðja, og við höfum eins og 5 og 7.

644
00:27:27,150 --> 00:27:31,440
Þegar þú bætir við þeim saman þér
fá 12, skipta þér um 2, er 6.

645
00:27:31,440 --> 00:27:33,726
>> Stundum er það erfitt að
útskýra hvers vegna það virkar,

646
00:27:33,726 --> 00:27:35,600
en ef þú vinnur í gegnum
dæmi stundum,

647
00:27:35,600 --> 00:27:37,962
það mun hjálpa þér að reikna út ef
það ætti að vera plús eða mínus.

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

649
00:27:38,846 --> 00:27:40,830
>> Nemandi: [inaudible]
nákvæmlega í miðju

650
00:27:40,830 --> 00:27:43,950
ef þeir höfðu að ræða þar
það er a einhver fjöldi af minni númer

651
00:27:43,950 --> 00:27:45,860
og eins og ein stór tala?

652
00:27:45,860 --> 00:27:49,750
>> Umsjón: Svo allt sem þú þarft
er miðja fylkisins.

653
00:27:49,750 --> 00:27:53,010
Svo ef þú átt fullt af litlum tölum
og síðan einn mjög stór tala

654
00:27:53,010 --> 00:27:54,799
í lok, er það ekki máli.

655
00:27:54,799 --> 00:27:56,840
Allt sem skiptir máli er að
þeir eru raðað, þú bara

656
00:27:56,840 --> 00:27:59,339
langar að horfa á miðju
array vegna þess að þú ert enn

657
00:27:59,339 --> 00:28:00,700
sneið vandamál í tvennt.

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
Svo nú er að við höfum
miðja, hvað gerum við næst?

661
00:28:06,430 --> 00:28:07,150
>> Nemandi: Bera saman.

662
00:28:07,150 --> 00:28:08,150
Umsjón: The bera saman.

663
00:28:08,150 --> 00:28:11,670
Svo bera miðsvæðið 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
Svo þú sérð hér að við höfum
þetta gildi við viljum hér.

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

668
00:28:22,012 --> 00:28:23,095
Muna þetta er fylki.

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

670
00:28:24,100 --> 00:28:26,970
Svo vísar miðja til vísitölu.

671
00:28:26,970 --> 00:28:29,785
Þannig að við viljum gera gildi miðju.

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

673
00:28:32,380 --> 00:28:35,650
Ekki gleyma ef þú vilt
að bera saman, tvöfaldir jafn.

674
00:28:35,650 --> 00:28:38,250
Þú gerir einn jafngildir þú ert
bara að fara að breyta henni,

675
00:28:38,250 --> 00:28:41,090
og þá, að sjálfsögðu, það er
fara að vera gildið sem þú vilt.

676
00:28:41,090 --> 00:28:42,300
Svo gera það ekki.

677
00:28:42,300 --> 00:28:44,350
>> Þannig að við erum að fara að sjá hvort
gildin á miðju

678
00:28:44,350 --> 00:28:46,460
er jöfn að verðmæti við viljum.

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

680
00:28:47,749 --> 00:28:48,790
Ekki gleyma axlabönd þínum.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox ætti að fara í burtu.

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

684
00:28:54,140 --> 00:28:56,200
Svo hvað eigum við að gera í þessu tilfelli?

685
00:28:56,200 --> 00:28:59,360
Ef það er það viljum við aftur?

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

687
00:29:01,510 --> 00:29:02,626
Við erum að reyna að segja.

688
00:29:02,626 --> 00:29:03,440
>> Nemandi: prenta út.

689
00:29:03,440 --> 00:29:05,314
>> Umsjón: Jæja, við
vil ekki að prenta út.

690
00:29:05,314 --> 00:29:08,220
Þannig að þetta er bool hér, svo vér
vilja til að fara aftur satt eða ósatt.

691
00:29:08,220 --> 00:29:12,280
Við erum að segja, er þetta númer
er [? RRA? ?] Svo ef það er,

692
00:29:12,280 --> 00:29:13,788
við aftur bara það satt.

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

694
00:29:16,780 --> 00:29:17,760
Ef ég getur stafa satt.

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

696
00:29:18,830 --> 00:29:20,805
>> Nemandi: Hvers vegna vildi þú ekki aftur núll?

697
00:29:20,805 --> 00:29:22,930
Umsjón: Svo þú gætir
skila núll ef þú vildir.

698
00:29:22,930 --> 00:29:26,780
En í þessu máli þar sem
Fallið okkar skilar bool,

699
00:29:26,780 --> 00:29:28,962
við þurfum að skila annað hvort sönn eða ósönn.

700
00:29:28,962 --> 00:29:30,920
Nemandi: Þegar þú ert
segja Boolean tjáningu,

701
00:29:30,920 --> 00:29:33,450
getur þú sett það jafn ósatt?

702
00:29:33,450 --> 00:29:39,860
Eins og ef ég á að segja, ef þetta ástand
er ekki fullnægt, eins er efri jafngildir ósatt.

703
00:29:39,860 --> 00:29:42,332
Mun það skilja ef þú bara
setja rangar á hinni hliðinni?

704
00:29:42,332 --> 00:29:43,040
Umsjón: Já.

705
00:29:43,040 --> 00:29:44,820
Svo reyndar ef þú ert
alltaf að gera eitthvað

706
00:29:44,820 --> 00:29:49,600
eins er efri eða lægri,
sem skilar satt eða ósatt

707
00:29:49,600 --> 00:29:53,850
og það er í raun slæmt stíl til
segjum jafnt jafnt satt eða jafn

708
00:29:53,850 --> 00:29:54,840
jafngildir falskur.

709
00:29:54,840 --> 00:30:00,210
Þú vilt nota þessi niðurstaða
eins sig sem stöðva þinn.

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

711
00:30:04,720 --> 00:30:05,860
Ekki það sem ég vildi.

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

713
00:30:08,150 --> 00:30:09,240
Það er það sem ég vildi.

714
00:30:09,240 --> 00:30:13,205
Svo í að ræða og þú ert að spyrja
um eitthvað svona vista þetta í c.

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

716
00:30:16,320 --> 00:30:25,150
>> Þannig að ef við höfum int helstu (tóm)
og eitthvað svona.

717
00:30:25,150 --> 00:30:31,922
Og þú hefur ef er efri
sumra inntak og þú ert

718
00:30:31,922 --> 00:30:33,630
spyrja hvort þú getur gert
eitthvað eins og þetta?

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

720
00:30:35,010 --> 00:30:35,679
Hægri?

721
00:30:35,679 --> 00:30:37,470
Nemandi: Ég var að reyna
að gera það [inaudible].

722
00:30:37,470 --> 00:30:38,450
Vegna þess að ef it's--

723
00:30:38,450 --> 00:30:39,200
Umsjón: Hægri.

724
00:30:39,200 --> 00:30:41,197
Svo þú vilt að þetta sé rangt, ekki satt?

725
00:30:41,197 --> 00:30:41,780
Nemandi: Já.

726
00:30:41,780 --> 00:30:45,960
Umsjón: Þannig að í þessu tilfelli þú
vilja það til að framkvæma ef það er ekki satt.

727
00:30:45,960 --> 00:30:50,510
Svo kaldur hlutur sem þú gerir það er þetta.

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

729
00:30:52,900 --> 00:30:55,650
Svo man upphrópunarmerki
lið negates hluti?

730
00:30:55,650 --> 00:30:58,270
Það segir [inaudible] þýðir ekki.

731
00:30:58,270 --> 00:31:03,590
Þannig að ef við skoðum bara
þessi hluti hér, að þú vilt

732
00:31:03,590 --> 00:31:05,740
segja að metur að
rangar eins og þú vilt hafa það til.

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

734
00:31:06,790 --> 00:31:09,880
Ekki rangar er sönn sem
þýðir þetta myndi framkvæma.

735
00:31:09,880 --> 00:31:11,037
Er að skynsamleg?

736
00:31:11,037 --> 00:31:11,620
Nemandi: Já.

737
00:31:11,620 --> 00:31:12,453
Umsjón: Awesome.

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
Þannig að við gætum bara aftur
satt í þessu tilviki.

741
00:31:16,330 --> 00:31:20,357
Svo nú höfum við tvö önnur
tilvik í þessu tilfelli.

742
00:31:20,357 --> 00:31:21,565
Hvað eru tveir aðrir mál okkar?

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

744
00:31:31,610 --> 00:31:32,900
Skulum bara gera það með þessum hætti.

745
00:31:32,900 --> 00:31:40,660
Svo skulum byrja á annað
Ef gildi á miðju

746
00:31:40,660 --> 00:31:43,230
er minna en gildið sem við viljum.

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

748
00:31:47,200 --> 00:31:52,020
Svo er gildi okkar í miðjunni minna
en gildið sem við erum að leita að.

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

750
00:31:53,765 --> 00:31:56,720
>> Svo sem bindur gera þér
held að við viljum uppfæra?

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

752
00:31:57,870 --> 00:31:58,780
Efri eða neðri?

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

754
00:32:01,440 --> 00:32:01,940
Upper?

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

756
00:32:03,230 --> 00:32:06,470
Svo sem megin í fylkinu
erum við að fara að vera að horfa á?

757
00:32:06,470 --> 00:32:07,500
>> Nemandi: Neðri.

758
00:32:07,500 --> 00:32:09,750
>> Umsjón: Við erum að fara
að vera að horfa á vinstri.

759
00:32:09,750 --> 00:32:11,120
Svo annað ef lítið gildi er minna.

760
00:32:11,120 --> 00:32:14,730
Svo miðju gildi þitt hér
er minna en það sem við viljum.

761
00:32:14,730 --> 00:32:17,202
Þannig að við viljum taka
Hægri hlið array okkar.

762
00:32:17,202 --> 00:32:18,910
Þannig að við erum að fara að
uppfæra neðri mörk okkar.

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

764
00:32:20,210 --> 00:32:23,020
Þannig að við munum endurúthluta okkar lægri.

765
00:32:23,020 --> 00:32:25,221
Og hvað finnst þér lægri ætti að vera?

766
00:32:25,221 --> 00:32:26,304
Nemandi: The Middle gildi?

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

768
00:32:27,446 --> 00:32:28,820
Umsjón: Svo miðja value--

769
00:32:28,820 --> 00:32:30,136
Nemandi: Plus 1.

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

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

772
00:32:32,300 --> 00:32:34,380
Getur einhver sagt mér hvers vegna
við höfum sem plús 1?

773
00:32:34,380 --> 00:32:35,730
>> Nemandi: [? No gildi?]
er jafnt því.

774
00:32:35,730 --> 00:32:36,120
>> Umsjón: Hægri.

775
00:32:36,120 --> 00:32:38,661
Þar sem við vitum nú þegar að
miðja gildi okkar er ekki jafnt og

776
00:32:38,661 --> 00:32:42,750
það og við viljum útiloka það
frá öllum síðari leitum.

777
00:32:42,750 --> 00:32:46,360
Ef þú gleymir að plús 1, þetta
verður eins lykkja endalaust.

778
00:32:46,360 --> 00:32:49,620
Og þú munt bara vera veiddur í
óendanlega lykkja og þá munt segfault

779
00:32:49,620 --> 00:32:50,370
og hlutirnir fara illa.

780
00:32:50,370 --> 00:32:54,780
Svo alltaf að tryggja að þú ert ekki
þ.mt gildi sem þú bara

781
00:32:54,780 --> 00:32:55,380
horfði á.

782
00:32:55,380 --> 00:32:58,530
Þannig að við að gæta um það með plús 1.

783
00:32:58,530 --> 00:33:04,840
>> Svo nú höfum við síðustu ástand okkar
sem ég alltaf fyrir öryggi sakir

784
00:33:04,840 --> 00:33:12,664
þú getur athugað hér, annars ef verð í
miðjunni er meiri en gildið

785
00:33:12,664 --> 00:33:13,163
við viljum.

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

787
00:33:16,260 --> 00:33:20,230
Það þýðir að við viljum
vinstri hönd hálfa.

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

789
00:33:21,350 --> 00:33:23,260
Svo sem einn erum við að fara að uppfæra?

790
00:33:23,260 --> 00:33:23,760
Efri.

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

792
00:33:25,470 --> 00:33:26,970
Og hvað er þetta einn að fara til að jafna?

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

794
00:33:31,630 --> 00:33:33,690
Middle mínus 1 vegna þess,
að sjálfsögðu, að við viljum

795
00:33:33,690 --> 00:33:38,370
að ganga úr skugga um að við erum ekki
horfa á þessi miðju gildi aftur.

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

797
00:33:41,830 --> 00:33:45,110
Og þá höfum við það.

798
00:33:45,110 --> 00:33:45,610
Það er hann.

799
00:33:45,610 --> 00:33:46,820
Það er allt tvöfaldur leit.

800
00:33:46,820 --> 00:33:48,190
Það er ekki svo slæmt, ekki satt?

801
00:33:48,190 --> 00:33:51,590
Það er eins og 10 línur af
kóðann með hvítt rúm.

802
00:33:51,590 --> 00:33:57,510
Svo mjög öflugur, mjög gagnlegt, þú verður
vera með það í eitt af síðari psets þínum.

803
00:33:57,510 --> 00:33:59,360
Kannski ekki þessu, en síðar.

804
00:33:59,360 --> 00:34:00,670
Svo að læra það.

805
00:34:00,670 --> 00:34:01,510
Elska það.

806
00:34:01,510 --> 00:34:02,980
Það mun við þig vel.

807
00:34:02,980 --> 00:34:05,370
Svo hjartarskinn einhver hafa allir
spurningar um tvöfaldur leit?

808
00:34:05,370 --> 00:34:06,196
Já.

809
00:34:06,196 --> 00:34:09,840
>> Nemandi: Skiptir máli
hvort n er jafnvel eða stakur?

810
00:34:09,840 --> 00:34:10,750
>> Umsjón: Nei

811
00:34:10,750 --> 00:34:18,150
Þar sem við kastaði það til miðju eins
int, það verður bara HÃ það.

812
00:34:18,150 --> 00:34:21,600
Þannig að það mun vera heiltölu og það mun
lokum raða í gegnum allt.

813
00:34:21,600 --> 00:34:23,909
Svo þú þarft ekki að hafa áhyggjur óður í það.

814
00:34:23,909 --> 00:34:24,580
Allir góður?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Ógnvekjandi.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Svo, þú krakkar fékk þetta.

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
Svo eins og við vorum að tala um, ég veit
David getið flókið runtimes.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Svo í besta tilfelli, það er bara
einn, sem við köllum föstu tíma.

825
00:34:50,340 --> 00:34:51,909
Getur einhver sagt mér hvers vegna það gæti verið?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Hvaða tegund af atburðarás væri að för með sér?

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
>> Nemandi: [inaudible] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
Umsjón: Svo miðju vera
Fyrsta þáttur sem við komum til, ekki satt?

833
00:35:03,830 --> 00:35:08,167
Svo annað hvort fylki eitt eða
hvað sem við erum að leita að bara

834
00:35:08,167 --> 00:35:09,750
gerist að vera smack DAB í miðju.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Svo er það besta mál okkar.

837
00:35:13,380 --> 00:35:17,540
Þú færð í alvöru vandamál, sennilega ekki
fara að ná [inaudible] að oft.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Hvað um versta tilfelli okkar?

840
00:35:19,750 --> 00:35:21,270
Versta tilfelli okkar er Log n.

841
00:35:21,270 --> 00:35:25,360
Og það hefur að gera með allt
veldi af tveimur hlutur sem ég talaði um.

842
00:35:25,360 --> 00:35:30,930
>> Svo í versta tilfelli myndi þýða
sem við þurftum að höggva array niður

843
00:35:30,930 --> 00:35:33,270
þar til það var þáttur í einn.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Þannig að við þurftum að höggva það niður í tvennt
eins oft og við gátum hugsanlega.

846
00:35:38,930 --> 00:35:41,430
Þess vegna er Log n vegna
þú halda bara deila með tveimur.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
So forsendum, hlutir sem þú
þarft að vita ef þú ert alltaf

849
00:35:45,830 --> 00:35:48,050
fara að nota tvöfaldur leit.

850
00:35:48,050 --> 00:35:50,680
Þætti þína verður raðað.

851
00:35:50,680 --> 00:35:53,890
Þeir verða að vera flokkaður því
það er eina leiðin sem þú

852
00:35:53,890 --> 00:35:57,060
getur vita ef þú ert fær um
að henda út hluta af því.

853
00:35:57,060 --> 00:36:00,260
>> Ef þú hefðir þetta jumbled poka
af tölum og þú ert að segja,

854
00:36:00,260 --> 00:36:05,380
OK, ég ætla að athuga miðjuna
númer og fjöldi ég er að leita að

855
00:36:05,380 --> 00:36:08,510
er minna en það, ég ætla bara að fara
að geðþótta henda út helming.

856
00:36:08,510 --> 00:36:11,130
Þú myndir ekki vita ef þú
tölur í síðarnefnda hluta.

857
00:36:11,130 --> 00:36:12,655
Listinn þarf að vera flokkaður.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Eins og vel, þetta getur verið
að fara á undan svolítið,

860
00:36:16,560 --> 00:36:18,360
en þú þarft að hafa handahófi aðgang.

861
00:36:18,360 --> 00:36:21,940
Þú þarft að vera fær til réttlátur
fara til miðju frumefni.

862
00:36:21,940 --> 00:36:25,110
Ef þú ert að fara
gegnum eitthvað

863
00:36:25,110 --> 00:36:28,630
eða það tekur þig auka skref
að fá til að miðju frumefni,

864
00:36:28,630 --> 00:36:31,750
það er ekki skráð þig n aftur því
þú ert að bæta meiri vinnu í það.

865
00:36:31,750 --> 00:36:34,800
Og þetta mun gera a lítill
meira vit í tvær vikur,

866
00:36:34,800 --> 00:36:37,950
en ég bara svona langaði til að formála,
gefa ykkur hugmynd um hvað er

867
00:36:37,950 --> 00:36:38,999
að koma.

868
00:36:38,999 --> 00:36:40,790
En þeir eru tveir
mikilvægar forsendur

869
00:36:40,790 --> 00:36:44,804
að þú þarft fyrir tvöfaldur lista.

870
00:36:44,804 --> 00:36:45,720
Gakktu úr skugga um að það er raðað.

871
00:36:45,720 --> 00:36:47,920
Það er ein stór fyrir
þú krakkar núna.

872
00:36:47,920 --> 00:36:52,170
Og að við getum farið inn í
restin af konar okkar.

873
00:36:52,170 --> 00:36:56,444
Svo fjórum sorts-- kúla,
innsetning, val og sameinast.

874
00:36:56,444 --> 00:36:57,485
Þeir eru allir góður af kaldur.

875
00:36:57,485 --> 00:37:02,860
Ef þú krakkar ákveða að taka CS 124,
þú munt læra óður í alls konar konar.

876
00:37:02,860 --> 00:37:07,575
Og ef þú ert XKCD aðdáandi, þar
er mjög flott grínisti um

877
00:37:07,575 --> 00:37:11,530
raunverulega eins árangurslaus konar, sem ég
mjög mæla með að þú að fara að horfa á.

878
00:37:11,530 --> 00:37:16,170
Einn af þeim er eins læti tagi, sem
er eins, ó nei, aftur handahófi fylkisins.

879
00:37:16,170 --> 00:37:16,991
Lokun kerfisins.

880
00:37:16,991 --> 00:37:17,490
Fara.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Svo er geeky húmor alltaf gott.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Svo er einhver man góður
af eins bara almenn hugmynd

885
00:37:25,750 --> 00:37:27,810
um hvernig kúla Raða virkar.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Þú manst?

888
00:37:32,155 --> 00:37:32,755
>> Nemandi: Já.

889
00:37:32,755 --> 00:37:33,970
>> Umsjón: Fara til það.

890
00:37:33,970 --> 00:37:38,980
>> Nemandi: Svo þú ert að fara í gegnum og
ef það er stærri, þá skipta um tvö.

891
00:37:38,980 --> 00:37:39,820
>> Umsjón: Mm-HM.

892
00:37:39,820 --> 00:37:40,564
Einmitt.

893
00:37:40,564 --> 00:37:41,730
Svo þú iterate bara í gegnum.

894
00:37:41,730 --> 00:37:43,050
Þú athuga tvær tölur.

895
00:37:43,050 --> 00:37:46,510
Ef sá áður er stærri
en einn eftir það,

896
00:37:46,510 --> 00:37:50,230
þú skipta bara þá svo að í
þessum hætti allar hærri tölur

897
00:37:50,230 --> 00:37:54,990
kúla upp undir lok listanum
og allir lægri tölur kúla niður.

898
00:37:54,990 --> 00:37:59,355
>> Átti hann að sýna ykkur kaldur
hljóði flokkun vídeó?

899
00:37:59,355 --> 00:38:00,480
Það er góður af kaldur.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Þannig Robert sagði bara, reiknirit
að þú stíga bara í gegnum listann,

902
00:38:05,200 --> 00:38:07,930
skipta aðliggjandi gildi
ef þeir eru ekki í röð.

903
00:38:07,930 --> 00:38:10,975
Og þá bara halda að endurtaka
þar til þú ekki gera neinar skiptasamninga.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Svo ekki slæmt, ekki satt?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Þannig að við höfum bara fljótur dæmi hér.

908
00:38:16,319 --> 00:38:18,360
Þannig að þetta er að fara að raða
þá í vaxandi röð.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Svo þegar við förum í gegnum fyrsta
tími, líta við í gegnum átta

911
00:38:23,470 --> 00:38:26,880
og sex eru augljóslega ekki
í röð, skipta við þá.

912
00:38:26,880 --> 00:38:27,985
>> Svo líta á næsta einn.

913
00:38:27,985 --> 00:38:29,430
Átta og fjórir ekki í röð.

914
00:38:29,430 --> 00:38:30,450
Skipta á þeim.

915
00:38:30,450 --> 00:38:32,530
Og svo átta og tveir, skipta á þeim.

916
00:38:32,530 --> 00:38:33,470
There við förum.

917
00:38:33,470 --> 00:38:39,519
Svo eftir fyrstu umferð, þú
vita að stærsti númerið þitt

918
00:38:39,519 --> 00:38:41,810
er að fara til vera alla leið
efst því það er bara

919
00:38:41,810 --> 00:38:44,210
fara að vera stöðugt
stærri en allt annað

920
00:38:44,210 --> 00:38:46,810
og það er bara að fara að kúla
upp alla leið til enda þar.

921
00:38:46,810 --> 00:38:48,226
Er að vit alla?

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
>> Svo þá við skoðum seinni okkar fara.

926
00:38:53,920 --> 00:38:54,980
Sex og fjórir, rofi.

927
00:38:54,980 --> 00:38:55,920
Sex og tveir, rofi.

928
00:38:55,920 --> 00:38:58,700
Og nú höfum við nokkur atriði í röð.

929
00:38:58,700 --> 00:39:02,240
Svo fyrir hvert skarðið sem við
gera í gegnum allt listanum okkar,

930
00:39:02,240 --> 00:39:06,320
við vitum að svona margar tölur
á enda, mun hafa verið flokkuð.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Svo við gerum þriðja framhjá,
sem er eitt skipti.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Og þá á fjórða okkar
líða, höfum við núll rifa.

935
00:39:15,910 --> 00:39:18,570
Og svo vitum við að okkar
array hefur verið raðað.

936
00:39:18,570 --> 00:39:20,900
>> Og það er stóra
hlutur með kúla tagi.

937
00:39:20,900 --> 00:39:23,720
Við vitum að þegar við
hafa núll skiptasamninga, að

938
00:39:23,720 --> 00:39:26,497
þýðir að allt
sé í fullkomnu röð.

939
00:39:26,497 --> 00:39:27,580
Það er góður af því hvernig við athugum.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Þannig að við erum líka að fara að kóða kúla
Raða sem einnig er ekki svo slæmt.

942
00:39:36,480 --> 00:39:38,120
Ekkert þessara eru svo slæmt.

943
00:39:38,120 --> 00:39:40,210
Ég veit að þeir geta virst svolítið skelfilegt.

944
00:39:40,210 --> 00:39:42,124
Ég veit þegar ég tók
bekknum, jafnvel þegar ég

945
00:39:42,124 --> 00:39:44,290
var að kenna bekknum um
í fyrsta sinn á síðasta ári,

946
00:39:44,290 --> 00:39:46,165
Ég var eins og, hvernig á ég að gera þetta?

947
00:39:46,165 --> 00:39:48,540
Það er vit í orði, en
hvernig gerum við í raun þetta?

948
00:39:48,540 --> 00:39:51,420
Hver er ástæða þess að ég vil líka að ganga
gegnum kóðann með ykkur hér.

949
00:39:51,420 --> 00:39:54,915
Svo ég hef sauðakóða
fyrir ykkur að þessu sinni.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Svo bara að halda þetta í huga sem
við erum að fara að umbreyta yfir.

952
00:39:58,970 --> 00:40:04,210
Þannig að við höfum sumir gegn sem
heldur utan um skiptasamninga okkar,

953
00:40:04,210 --> 00:40:08,370
vegna þess að við þurfum að ganga úr skugga um
að við erum að athuga það.

954
00:40:08,370 --> 00:40:11,830
Og við iterate Fylkið
eins og við gerðum bara með þessu dæmi.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Ef þáttur áður er stærri en
þátturinn eftir hvar við erum á,

957
00:40:17,325 --> 00:40:20,760
við skipta á þeim og við hækka OKKAR
gegn því eins fljótt og við skipta,

958
00:40:20,760 --> 00:40:23,850
Við viljum láta gegn okkar vita það.

959
00:40:23,850 --> 00:40:26,247
Einhverjar spurningar þarna?

960
00:40:26,247 --> 00:40:27,580
Eitthvað virðist fyndið hérna.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
Nemandi: Ert þú sett teljarann ​​á núll
hvert skipti sem þú ferð í gegnum lykkjuna?

963
00:40:32,350 --> 00:40:34,339
Ert þú ekki að halda áfram
aftur til núll í hvert skipti?

964
00:40:34,339 --> 00:40:35,505
Umsjón: Ekki endilega.

965
00:40:35,505 --> 00:40:39,710
Svo það sem gerist er að við að fara í gegnum hér.

966
00:40:39,710 --> 00:40:43,830
Svo að gera á meðan, muna, þetta
mun framkvæma einu án mistakast.

967
00:40:43,830 --> 00:40:46,480
Svo það er að fara til að stilla
gegn jafnt og núll,

968
00:40:46,480 --> 00:40:48,070
þá er það að fara að iterate gegnum.

969
00:40:48,070 --> 00:40:50,590
Eins og það iterates gegnum,
það mun uppfæra teljara.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Eins og það endurnýja gegn, þegar það er gert,
þegar það er náð enda fylkisins,

972
00:40:56,900 --> 00:41:00,830
Ef listinn okkar hefur ekki verið raðað,
gegn mun hafa verið uppfærð.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Svo þá fer það ástand og það
segir, OK, er gegn hærri en núll.

975
00:41:07,150 --> 00:41:09,290
Ef það er, gera það aftur.

976
00:41:09,290 --> 00:41:14,340
Þú vilt endurstilla svo að þegar þú
fara í gegnum, gegn er jafnt og núll.

977
00:41:14,340 --> 00:41:18,240
Ef þú ferð í gegnum a Raðað
array, ekkert breytist,

978
00:41:18,240 --> 00:41:21,355
það tekst ekki, og þú
skila raðað lista.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Er það er vit?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
Nemandi: Það gæti í smá.

983
00:41:26,356 --> 00:41:27,147
Umsjón: OK.

984
00:41:27,147 --> 00:41:28,980
Ef það er einhver annar
Spurningin sem kemur upp.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Já.

987
00:41:30,680 --> 00:41:33,760
>> Nemandi: Hvað myndi virka
vera fyrir skipta þætti?

988
00:41:33,760 --> 00:41:36,900
>> Umsjón: Svo við getum raunverulega skrifað
að ef við erum að fara að núna.

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
Svo á að huga, Alison er að fara
að skipta aftur yfir á tækið.

992
00:41:42,155 --> 00:41:43,080
Það er að fara að vera skemmtilegt.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Og við höfum Nice okkar
kúla Raða hlutur hér.

995
00:41:47,390 --> 00:41:50,800
Svo ég gerði þegar hjólreiðar
gegnum array.

996
00:41:50,800 --> 00:41:53,030
Við höfum skiptasamninga okkar að
eru jafnt og núll.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Þannig að við viljum skipta við hliðina
þættir ef þeir eru út af röð.

999
00:41:58,440 --> 00:42:03,020
Svo það fyrsta sem við þurfum að
gera er kunnugt gegnum fylking okkar.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Svo hvernig heldurðu að við gæti
iterate gegnum fylking okkar?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Við höfum fyrir og ég er 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Við viljum i að vera minna
en n mínus 1 mínus k.

1006
00:42:22,454 --> 00:42:23,870
Og ég skal útskýra það í annað.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Svo er þetta hagræðingu hér þar,
man hvernig ég sagði eftir hvert skarðið

1009
00:42:32,830 --> 00:42:36,655
gegnum array vér
veit að allt sem er on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Svo eftir einni umferð við
vita að þetta er flokkað.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Eftir tvær umferðir við vitum
að allt þetta er raðað.

1014
00:42:50,060 --> 00:42:52,750
Eftir þrjár umferðir við
veit það er raðað.

1015
00:42:52,750 --> 00:42:55,620
Þannig að hvernig ég ætla iterating
gegnum array hér,

1016
00:42:55,620 --> 00:43:01,090
er það er að gera viss um að aðeins að fara
gegnum það sem við vitum er óflokkuðum.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Það er bara um hagræðingu.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Þú getur skrifað það naively bara
iterating gegnum allt,

1021
00:43:08,210 --> 00:43:09,970
það myndi bara taka lengri tíma.

1022
00:43:09,970 --> 00:43:12,470
Með þessu fjórum lykkja það er
bara ágætur hagræðingu

1023
00:43:12,470 --> 00:43:18,460
vegna þess að við vitum að eftir hvert fullur
endurtekning gegnum array hér,

1024
00:43:18,460 --> 00:43:24,050
eins og sérhver fullur lykkja hér, við vitum
að ein fleiri af þessum þáttum

1025
00:43:24,050 --> 00:43:25,760
verður raðað í lokin.

1026
00:43:25,760 --> 00:43:28,294
>> Þannig að við þurfum ekki að hafa áhyggjur óður í þá.

1027
00:43:28,294 --> 00:43:29,710
Er að vit alla?

1028
00:43:29,710 --> 00:43:30,950
Þessi kaldur lítið bragð?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Svo í því tilfelli, ef
við erum iterating gegnum,

1031
00:43:37,270 --> 00:43:50,590
við vitum að við viljum athuga hvort
array n og n plús 1 eru í því skyni.

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
Svo hér er sauðakóða.

1035
00:43:54,600 --> 00:43:57,540
Við viljum athuga hvort array n
og n auk 1 eru í röð.

1036
00:43:57,540 --> 00:43:59,520
Svo hvað gæti við höfum það?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Það er að fara að vera einhver skilyrt.

1039
00:44:03,120 --> 00:44:04,220
Það mun vera ef.

1040
00:44:04,220 --> 00:44:07,066
>> Nemandi: Ef array n er
minna en array n plús 1.

1041
00:44:07,066 --> 00:44:07,816
Umsjón: Mm-HM.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Jæja, minna en eða meira en.

1044
00:44:10,699 --> 00:44:11,615
Nemandi: Greater en.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Þá viljum við að skipta á þeim.

1047
00:44:17,620 --> 00:44:18,570
Einmitt.

1048
00:44:18,570 --> 00:44:23,570
Svo nú erum við að fá í það er
Orsakir skipta þá?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Þannig að við fórum í gegnum þetta stutta stund,
a tegund skiptasamninga virka í síðustu viku.

1051
00:44:28,137 --> 00:44:29,595
Hefur einhver man hvernig það unnið?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Þannig að við getum ekki bara endurúthluta þeim, ekki satt?

1054
00:44:34,950 --> 00:44:36,640
Vegna þess að einn af þeim mun villast.

1055
00:44:36,640 --> 00:44:41,696
Ef við því að áðurnefnt A er jöfn og B og síðan að b
er jafnt og A, allt í einu þau bæði

1056
00:44:41,696 --> 00:44:43,150
eru bara jafn B.

1057
00:44:43,150 --> 00:44:45,720
>> Svo það sem við þurfum að gera er að við
hafa tímabundið breytu sem er

1058
00:44:45,720 --> 00:44:49,055
að fara að halda eitt af okkar stund
við erum í því ferli að skipta.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Svo það sem við höfum er að við munum hafa sumir int
afleysingamanneskja er jafn to-- þú geta framselja það

1061
00:44:56,464 --> 00:44:59,130
til hvort sem þú vilt, bara
vertu viss um að þú halda utan um it--

1062
00:44:59,130 --> 00:45:01,840
svo í þessu tilfelli, ég ætla að
framselja það til array n plús 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Svo það er að fara að halda hvað sem
gildi er í þeirri seinni blokk

1065
00:45:07,674 --> 00:45:08,590
að við erum að horfa á.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Og þá getum við gert er að við getum farið
undan og endurúthluta array n plús 1,

1068
00:45:13,240 --> 00:45:14,990
vegna þess að við vitum að við
hafa þessi gildi eru geymdar.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Þetta er einnig einn af the stór
things-- Ég veit ekki hvort einhver ykkar

1071
00:45:19,270 --> 00:45:23,780
haft mál þar sem ef þú skiptir tvo
línur af kóða skyndilega hlutirnir virkuðu.

1072
00:45:23,780 --> 00:45:25,880
Order er mjög mikilvægt í CS.

1073
00:45:25,880 --> 00:45:29,450
Svo tryggja þú skýringarmynd
hlutina út ef mögulegt

1074
00:45:29,450 --> 00:45:31,230
um hvað er í raun að gerast.

1075
00:45:31,230 --> 00:45:34,256
Svo nú erum við að fara að
endurúthluta array n plús 1,

1076
00:45:34,256 --> 00:45:36,005
vegna þess að við vitum að við
hafa þessi gildi eru geymdar.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Og við getum falið að til array
n eða í þessu tilfelli array i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Of margar breytur.

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
Svo nú höfum við færður array I
plús 1 til að jafna það er fylkt i.

1084
00:46:01,500 --> 00:46:08,240
Og nú getum við farið til baka og
úthluta array ég við það?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Einhver?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> Nemandi: 10.

1089
00:46:14,010 --> 00:46:14,680
>> Umsjón: 10.

1090
00:46:14,680 --> 00:46:15,180
Einmitt.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Og eitt síðasta hlutur.

1093
00:46:18,640 --> 00:46:21,840
Ef við höfum skipst það nú,
Hvað þurfum við að gera?

1094
00:46:21,840 --> 00:46:23,740
Hvað er eitt
það er að fara að segja okkur

1095
00:46:23,740 --> 00:46:27,542
ef við segja alltaf þetta forrit?

1096
00:46:27,542 --> 00:46:29,250
Hvað segir okkur að við
hafa raðað lista?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Ef við gerum framkvæma neinar skiptasamninga, ekki satt?

1099
00:46:33,750 --> 00:46:36,900
Ef skiptasamninga er jafnt og
núll í lok þessa.

1100
00:46:36,900 --> 00:46:42,975
Svo þegar þú framkvæma skipti, eins og vér
bara gerði hér, viljum við að uppfæra skiptasamninga.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Og ég veit að það var
spurning áðan um getur þú

1103
00:46:47,210 --> 00:46:49,689
nota núll eða einn stað
af satt eða ósatt.

1104
00:46:49,689 --> 00:46:50,980
Og það er það sem þetta gerir hér.

1105
00:46:50,980 --> 00:46:52,750
Svo segir þetta ef ekki skiptasamninga.

1106
00:46:52,750 --> 00:47:01,310
Svo ef skiptasamninga er núll, sem is-- ég alltaf
fá sannleika mínir og falses mínir ruglað.

1107
00:47:01,310 --> 00:47:03,960
Við viljum okkur að meta
true og það er ekki.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Þannig að ef það er núll, þá er það ósatt.

1110
00:47:09,630 --> 00:47:12,560
Ef þú ógilt það með a
[? Bang?] það verður satt.

1111
00:47:12,560 --> 00:47:13,975
Svo þá keyrir þessa línu.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Sannleikur og ósatt
núll og sjálfur fá brjálaður.

1114
00:47:17,370 --> 00:47:20,690
Bara ef þú gengur hægt
gegnum það að það mun gera vit.

1115
00:47:20,690 --> 00:47:23,320
En það er það sem þetta litla
bita af kóða hér gerir.

1116
00:47:23,320 --> 00:47:26,490
Svo athugar þetta að sjá
höfum við gert neinar skiptasamninga.

1117
00:47:26,490 --> 00:47:30,054
Þannig að ef það er eitthvað að auki
núll, það er að fara að vera falskur

1118
00:47:30,054 --> 00:47:31,970
og the heild hlutur er
fara að framkvæma aftur.

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
>> Nemandi: Hvað er Break gera?

1123
00:47:36,000 --> 00:47:38,990
>> Umsjón: Brot bara
brýtur þig út úr lykkja.

1124
00:47:38,990 --> 00:47:41,570
Þannig að í þessu tilfelli hefði það
bara dauðdagi forritið

1125
00:47:41,570 --> 00:47:43,828
og þú myndir bara
hafa raðað lista þinn.

1126
00:47:43,828 --> 00:47:44,536
Nemandi: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
Umsjón: Fyrirgefðu?

1129
00:47:49,010 --> 00:47:52,110
Nemandi: Þar áður við
notuð skrifað 1 yfir skriflega núll

1130
00:47:52,110 --> 00:47:54,170
að kynna að ef
sem vilja vinna eða ekki.

1131
00:47:54,170 --> 00:47:54,878
>> Umsjón: Já.

1132
00:47:54,878 --> 00:47:56,410
Svo er hægt að fara aftur núll eða 1.

1133
00:47:56,410 --> 00:47:58,950
Í þessu tilfelli, vegna þess að við erum í raun ekki
gera neitt með virkni,

1134
00:47:58,950 --> 00:48:00,150
við viljum bara það að brjóta.

1135
00:48:00,150 --> 00:48:02,680
Við gerum í raun ekki sama um það.

1136
00:48:02,680 --> 00:48:06,960
Brake er einnig gott ef
það er notað til að brjóta út

1137
00:48:06,960 --> 00:48:10,710
af fjórum lykkjur eða aðstæður sem
þú vilt ekki að halda framkvæmd.

1138
00:48:10,710 --> 00:48:12,110
Það tekur bara þig út af þeim.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Það er a hluti af a Litbrigði hlutur.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Mér finnst eins og það er
a einhver fjöldi af hendi veifa,

1143
00:48:18,445 --> 00:48:19,740
eins og þú munt læra um þetta fljótlega.

1144
00:48:19,740 --> 00:48:20,955
>> En þú munt læra um þetta fljótlega.

1145
00:48:20,955 --> 00:48:21,500
Ég lofa.

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
Svo þýðir allir fá kúla tagi?

1149
00:48:24,840 --> 00:48:25,550
Ekki of slæmt.

1150
00:48:25,550 --> 00:48:31,910
Iterate gegnum, Víxla hlutina með a
afleysingamanneskja breytu, og við erum öll sett þar?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Ógnvekjandi.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Til baka í PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Einhverjar spurningar almennt
um þessum svo langt?

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
>> Nemandi: [inaudible] int helstu venjulega.

1162
00:48:45,279 --> 00:48:46,695
Ert þú þarft að hafa að fyrir þetta?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> Umsjón: Þannig að við vorum bara að horfa
bara á raunverulegri flokkunarstöð reiknirit.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Ef þú hefðir það í
eins stærri áætlun,

1167
00:48:56,350 --> 00:48:57,891
þú vildi hafa int helstu einhversstaðar.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Fer eftir því hvar þú
nota þessa reiknirit,

1170
00:49:02,880 --> 00:49:05,860
það myndi ákveða hvað er
verið skilað af henni.

1171
00:49:05,860 --> 00:49:09,960
En fyrir okkar tilviki erum við stranglega
horfa á hvernig virkar þetta í raun

1172
00:49:09,960 --> 00:49:11,300
iterate gegnum fjölda.

1173
00:49:11,300 --> 00:49:12,570
Svo við ekki hafa áhyggjur óður í það.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Þannig að við vorum að tala um besta tilfelli og
versta veg fyrir tvöfaldur leit.

1176
00:49:19,830 --> 00:49:22,470
Svo það er einnig mikilvægt að gera
að fyrir hvert konar okkar.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Svo er það finnst þér það versta
ræða afturkreistingur af kúla tagi?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Þú krakkar muna?

1181
00:49:30,700 --> 00:49:31,784
>> Nemandi: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
Umsjón: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Svo það þýðir að það eru
n mínus 1 samanburð.

1184
00:49:35,070 --> 00:49:40,060
Svo er eitt að gera sér grein fyrir
að á fyrsta endurtekning,

1185
00:49:40,060 --> 00:49:43,360
við förum í gegnum, bera saman við
þessir two-- svo er það 1.

1186
00:49:43,360 --> 00:49:46,685
Þessir tveir, þrír, fjórir.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Svo eftir eina endurtekning við
þegar hafa fjórar samanburð.

1189
00:49:55,050 --> 00:49:58,230
Þegar ég er að tala um afturkreistingur og n.

1190
00:49:58,230 --> 00:50:04,680
N táknar fjölda samanburð
sem fall af hvernig margir þættir

1191
00:50:04,680 --> 00:50:05,570
við höfum.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Svo við förum í gegnum, við höfum fjóra.

1194
00:50:08,860 --> 00:50:11,780
Í næsta skipti sem þú veist að við gerum ekki
að taka thessu.

1195
00:50:11,780 --> 00:50:15,140
Við berum saman þessar tvær,
þessir tveir, þessir tveir,

1196
00:50:15,140 --> 00:50:20,050
og ef við ekki hafa að hagræðingar
með fjórum lykkju sem ég skrifaði,

1197
00:50:20,050 --> 00:50:22,750
þú vildi vera að bera saman hér engu að síður.

1198
00:50:22,750 --> 00:50:26,170
Svo þú þyrftir að
hlaupa í gegnum array

1199
00:50:26,170 --> 00:50:34,380
og gera n samanburð n
sinnum, vegna þess að í hvert skipti sem

1200
00:50:34,380 --> 00:50:36,670
hlaupa í gegnum það sem við flokkunarröð eitt.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Og í hvert skipti sem við hlaupa í gegnum
array, gera við n samanburð.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Svo er afturkreistingur okkar fyrir þetta
í raun n í öðru veldi, sem

1205
00:50:46,330 --> 00:50:48,400
er miklu verra í okkar
log enda vegna þess að það

1206
00:50:48,400 --> 00:50:51,965
þýðir að ef við hefðum fjóra
milljarða frumefni, það er

1207
00:50:51,965 --> 00:50:55,260
að fara að taka okkur fjóra milljarða
veldi í stað 32.

1208
00:50:55,260 --> 00:51:01,240
Svo ekki besta afturkreistingur,
en fyrir sumum hlutum,

1209
00:51:01,240 --> 00:51:04,610
þú veist, ef þú ert innan
ákveðnum fjölda þátta

1210
00:51:04,610 --> 00:51:06,540
kúla Raða kann vera í lagi að nota.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Svo nú er það besta málið afturkreistingur?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
Nemandi: Zero?

1215
00:51:14,940 --> 00:51:16,420
Eða 1?

1216
00:51:16,420 --> 00:51:18,140
>> Umsjón: So 1 myndi
vera einn samanburður.

1217
00:51:18,140 --> 00:51:19,114
Hægri.

1218
00:51:19,114 --> 00:51:20,002
>> Nemandi: N mínus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> Umsjón: Svo, já.

1221
00:51:22,320 --> 00:51:22,990
Svo n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Alltaf þegar þú ert með hugmynd eins N
mínus 1, við hafa tilhneigingu til að bara sleppa henni

1223
00:51:26,510 --> 00:51:31,680
og við segjum bara n vegna þess að þú ert
að bera saman hvert these-- hvert par.

1224
00:51:31,680 --> 00:51:36,470
Svo það væri n mínus 1, sem við
við myndum bara segja er um n.

1225
00:51:36,470 --> 00:51:39,280
Þegar þú ert að takast á við afturkreistingur,
allt er í samsvari.

1226
00:51:39,280 --> 00:51:43,860
Svo lengi sem veldisvísirinn er
rétt, þú ert nokkuð góður.

1227
00:51:43,860 --> 00:51:45,700
>> Það er hvernig við takast á við það.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Þannig að besta málið sé n, sem
þýðir að listinn er nú þegar raðað,

1230
00:51:51,780 --> 00:51:54,320
og allt sem við gerum er að keyra í gegnum
og athuga hvort það er raðað.

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
Allt í lagi.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Svo eins og þú sérð hér, við
bara hafa fleiri myndrit.

1236
00:52:01,920 --> 00:52:02,660
Svo n veldi.

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
Miklu verra en n eins og við sjáum, og
miklu, miklu verri en log 2n.

1240
00:52:09,730 --> 00:52:12,060
Og þá færðu líka inn log logs.

1241
00:52:12,060 --> 00:52:18,020
Og þú tekur 124, þá færðu inn
eins log stjörnu, sem er eins og brjálaður.

1242
00:52:18,020 --> 00:52:20,172
Svo ef þú hefur áhuga,
leit Log stjarna.

1243
00:52:20,172 --> 00:52:20,880
Það er góður af gaman.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Svo við höfum þetta mikla töfluna.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Bara höfuð upp, þetta a
dásamlegt Mynd til að hafa

1248
00:52:28,720 --> 00:52:31,350
um miðjan tíma þínum vegna þess að við
lengi til að spyrja þig þessar thins.

1249
00:52:31,350 --> 00:52:36,090
Svo bara höfuð upp, þetta á þinn
miðannar á fallegu svindlari lak

1250
00:52:36,090 --> 00:52:36,616
þar.

1251
00:52:36,616 --> 00:52:37,990
Svo við horfði bara á kúla tagi.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Versta tilfelli, n veldi, besta tilfelli, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Og við erum að fara að horfa á aðra.

1256
00:52:44,950 --> 00:52:47,940
>> Og eins og þú geta sjá, eina
sá sem raunverulega gerir vel

1257
00:52:47,940 --> 00:52:50,910
er Mergesort, sem við munum fá inn af hverju.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Þannig að við erum að fara að fara á
Næsta einn here-- val tagi.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Hefur einhver man hvernig
val Raða unnið?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Að fara í það.

1264
00:53:05,700 --> 00:53:08,210
>> Nemandi: grundvallaratriðum fara í gegnum
fyrirmæli og búa til nýjan lista.

1265
00:53:08,210 --> 00:53:11,001
Og rétt eins og þú ert að setja þætti
í, setja þá á réttum stað

1266
00:53:11,001 --> 00:53:11,750
í nýju skránni.

1267
00:53:11,750 --> 00:53:14,040
>> Umsjón: Svo að hljóð
meira eins Innsetningarröðun.

1268
00:53:14,040 --> 00:53:15,040
En þú ert mjög nálægt.

1269
00:53:15,040 --> 00:53:15,915
Þeir eru mjög svipuð.

1270
00:53:15,915 --> 00:53:17,440
Jafnvel ég fá þá ruglað stundum.

1271
00:53:17,440 --> 00:53:18,981
Fyrir þessa kafla sem ég var eins og, bíddu.

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
Svo það sem þú vilt
gera er val tagi,

1275
00:53:24,141 --> 00:53:25,890
hvernig hægt er að hugsa
um það og hvernig

1276
00:53:25,890 --> 00:53:30,140
Ég tryggt að ég reyni ekki að fá
þá ruglað, er það fer í gegnum

1277
00:53:30,140 --> 00:53:33,280
og það velur
minnsti fjöldi og það

1278
00:53:33,280 --> 00:53:36,070
setur það í upphafi á listanum þínum.

1279
00:53:36,070 --> 00:53:37,730
Það skiptir það með því fyrsta staðnum.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Þeir hafa í raun dæmi fyrir mig.

1282
00:53:45,370 --> 00:53:46,540
Ógnvekjandi.

1283
00:53:46,540 --> 00:53:50,130
Svo bara leið til að hugsa um it-- val
raða, velja minnstu gildi.

1284
00:53:50,130 --> 00:53:51,940
Og við erum að fara að
hlaupa í gegnum dæmi

1285
00:53:51,940 --> 00:53:55,320
að ég tel að muni hjálpa því
Ég held myndefni alltaf hjálpa.

1286
00:53:55,320 --> 00:53:58,510
Svo erum við að byrja út með eitthvað
það er alveg óflokkað.

1287
00:53:58,510 --> 00:54:00,730
Red verður óflokkuðu,
Grænn verður raðað.

1288
00:54:00,730 --> 00:54:02,190
Það mun allt vit í annað.

1289
00:54:02,190 --> 00:54:08,950
>> Svo við förum í gegnum og við iterate
frá upphafi til enda.

1290
00:54:08,950 --> 00:54:12,320
Og við segjum, OK, 2 er
minnsti fjöldi okkar.

1291
00:54:12,320 --> 00:54:15,680
Þannig að við erum að fara að taka 2 og við erum að fara
að færa það til the andlit af array okkar

1292
00:54:15,680 --> 00:54:17,734
því það er
minnsti fjöldi sem við höfum.

1293
00:54:17,734 --> 00:54:19,150
Svo það er það sem þetta er að gera hér.

1294
00:54:19,150 --> 00:54:20,820
Það er bara að fara að skipta þessum tveimur.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Svo nú höfum við a raðað
hluti og óflokkuðum hluta.

1297
00:54:25,450 --> 00:54:27,810
Og hvað er gott að muna
um val tagi

1298
00:54:27,810 --> 00:54:30,690
er að við erum aðeins að velja
frá óflokkaðs hluta.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> The Raðað hluti þú skilur bara einn.

1301
00:54:34,527 --> 00:54:35,660
Mm-HM?

1302
00:54:35,660 --> 00:54:38,452
>> Nemandi: Hvernig virkar það vita hvað er
minnstu án bera það

1303
00:54:38,452 --> 00:54:39,868
að öll önnur gildi í array.

1304
00:54:39,868 --> 00:54:41,250
Umsjón: Það gerir bera það.

1305
00:54:41,250 --> 00:54:42,041
Við eins sleppt því.

1306
00:54:42,041 --> 00:54:43,850
Þetta er bara almenn heild.

1307
00:54:43,850 --> 00:54:44,831
Já.

1308
00:54:44,831 --> 00:54:47,205
Þegar við að skrifa kóðann sem ég ætla
viss um að þú munt vera fleiri ánægðir.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
En þú vistar fyrst
þáttur sem minnstu.

1311
00:54:53,030 --> 00:54:56,110
Að bera og þú
segja, OK, er það minni?

1312
00:54:56,110 --> 00:54:56,660
Já.

1313
00:54:56,660 --> 00:54:57,460
Hafðu það.

1314
00:54:57,460 --> 00:54:58,640
Hér er það minni?

1315
00:54:58,640 --> 00:54:59,660
Nei?

1316
00:54:59,660 --> 00:55:02,510
>> Þetta er minnsti þinn,
breyta henni til gildi.

1317
00:55:02,510 --> 00:55:06,340
Og þú munt vera miklu ánægðari
þegar við förum í gegnum kóðann.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Svo við förum í gegnum, skipta við það, svo þá
Við lítum á þetta óflokkuðum hluta.

1320
00:55:13,970 --> 00:55:15,810
Þannig að við erum að fara að velja þremur.

1321
00:55:15,810 --> 00:55:18,890
Við erum að fara að setja það á á
enda flokkaðs hluta okkar.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Og við erum bara að fara að halda að gera
að gera það, og gera það.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Svo er af þessu tagi okkar sauðakóða hér.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Við munum kóða það upp hér í annað.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
En bara eitthvað að ganga
gegnum á háu stigi.

1330
00:55:37,270 --> 00:55:40,275
Þú ert að fara að fara frá
Ég er 0 til n mínus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Það er önnur fínstillingu.

1333
00:55:43,530 --> 00:55:45,020
Ekki hafa áhyggjur of mikill óður í það.

1334
00:55:45,020 --> 00:55:46,620
Svo eins og þú varst að segja.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Eins Jakob var að segja, hvernig vér
halda utan um hvað lágmarki okkar er?

1337
00:55:54,406 --> 00:55:55,030
Hvernig vitum við?

1338
00:55:55,030 --> 00:55:57,060
Við verðum að bera saman
allt í listanum okkar.

1339
00:55:57,060 --> 00:55:59,600
>> Svo lágmarki jafngildir i.

1340
00:55:59,600 --> 00:56:03,870
Það er bara að segja í þessu tilfelli
vísitölu lágmarksgildi okkar.

1341
00:56:03,870 --> 00:56:07,660
Svo þá er það að fara að iterate gegnum
og það fer frá J er jafnt ég plús 1.

1342
00:56:07,660 --> 00:56:11,420
Þannig að við vitum nú þegar að
sem er fyrsta þáttur okkar.

1343
00:56:11,420 --> 00:56:13,240
Við þurfum ekki að bera saman það að sjálfu sér.

1344
00:56:13,240 --> 00:56:16,970
Svo erum við að byrja að bera saman það til the næstur
einn sem er hvers vegna það er ég auk 1 til N

1345
00:56:16,970 --> 00:56:20,110
mínus 1, sem er
enda fylkisins þar.

1346
00:56:20,110 --> 00:56:25,090
Og við sögðum ef array á
j er minna en array min,

1347
00:56:25,090 --> 00:56:29,200
þá erum endurúthluta hvar
lágmarkskröfur vísitölur okkar er.

1348
00:56:29,200 --> 00:56:37,470
>> Og ef mín er ekki jafnt og i, eins og
í þar sem við vorum aftur hérna.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Svo eins og þegar við gerðum fyrst þetta einn.

1351
00:56:41,790 --> 00:56:49,310
Í þessu tilviki, að það myndi byrja á
núll, það myndi enda upp tilvera tvö.

1352
00:56:49,310 --> 00:56:53,010
Svo mín myndi ekki jafn i í lokin.

1353
00:56:53,010 --> 00:56:55,720
Sem leyfir okkur að vita að
við þurfum að skipta á þeim.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Mér líður eins og steypu dæmi
mun hjálpa mikið meira en þetta.

1356
00:57:00,470 --> 00:57:04,970
Svo ég ætla að kóða þetta upp með ykkur
núna og held ég að það verður að vera betra.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Konar tilhneigingu til að vinna þannig í því
það er oft betra bara að sjá þær.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Svo það sem við viljum gera er
við viljum fyrst minnstu

1361
00:57:17,280 --> 00:57:19,890
þáttur í stöðu sinni í array.

1362
00:57:19,890 --> 00:57:21,280
Einmitt það Jakob var að segja.

1363
00:57:21,280 --> 00:57:23,090
Þú þarft að geyma það á einhvern hátt.

1364
00:57:23,090 --> 00:57:25,900
Þannig að við erum að fara að byrja hér
iterating yfir array.

1365
00:57:25,900 --> 00:57:28,970
Við erum að fara að segja að það er okkar
fyrsta bara til að byrja með.

1366
00:57:28,970 --> 00:57:38,308
Þannig að við erum að fara að hafa int
minnstu er jafnt og array á i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Svo eitt að taka eftir, á hverjum
skipti sem þetta lykkja keyrir,

1369
00:57:45,050 --> 00:57:48,550
við erum að byrja einu skrefi lengra.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Þegar við byrjum að líta á þetta einn.

1372
00:57:57,440 --> 00:58:00,840
Næst þegar við iterate gegnum,
við erum farin á þessu einn

1373
00:58:00,840 --> 00:58:02,680
og framselja það minnsta gildi okkar.

1374
00:58:02,680 --> 00:58:10,450
Svo það er mjög svipað og kúla tagi
þar sem við vitum að eftir einni umferð,

1375
00:58:10,450 --> 00:58:11,700
þetta síðasta þáttur er flokkaður.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Með val tagi,
það er bara hið gagnstæða.

1378
00:58:15,120 --> 00:58:18,950
>> Á hverjum skarðinu, við vitum að
sá fyrsti er raðað.

1379
00:58:18,950 --> 00:58:21,360
Eftir seinni skarðið, sem
seinni verður raðað.

1380
00:58:21,360 --> 00:58:26,470
Og eins og þú sást við glæruna dæmi,
raðað hluti okkar heldur bara áfram að stækka.

1381
00:58:26,470 --> 00:58:34,020
Svo með því að setja minnstu einn okkar
til fylki i, allt það er að gera

1382
00:58:34,020 --> 00:58:37,340
er að þrengja það
við erum að horfa á svo sem

1383
00:58:37,340 --> 00:58:40,164
til að draga úr fjölda
samanburða við tökum.

1384
00:58:40,164 --> 00:58:41,770
Er að gera skilningarvit til alla?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Ert þú þarft mig að hlaupa í gegnum það
aftur hægari eða í mismunandi orðum?

1387
00:58:46,380 --> 00:58:47,180
Ég er fús til að.

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
>> Þannig að við erum að geyma
gildi á þessum tímapunkti,

1392
00:58:55,540 --> 00:58:57,840
en við viljum líka að geyma vísitölu.

1393
00:58:57,840 --> 00:59:01,010
Þannig að við erum að fara að geyma
staða minnstu

1394
00:59:01,010 --> 00:59:02,770
einn, sem er bara að fara að vera i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Svo nú er Jakob sáttur.

1397
00:59:05,440 --> 00:59:06,870
Við höfum hluti geymdar.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Og nú þurfum við að horfa í gegnum
sem óflokkuðu hluti fylkisins.

1400
00:59:11,870 --> 00:59:18,170
Þannig að í þessu tilfelli
væri óflokkuðum okkar.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Þetta er 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
>> Svo það sem við erum að fara að gera
er að fara að vera fyrir lykkju.

1406
00:59:30,040 --> 00:59:32,066
Alltaf þegar þú þarft að
iterate gegnum fjölda,

1407
00:59:32,066 --> 00:59:33,440
hugur þinn gæti farið til lykkju.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Svo fyrir einhverjum int k
equals-- hvað við hugsum

1410
00:59:38,090 --> 00:59:39,700
k er að fara til að jafna til að byrja með?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Þetta er það sem við setjum sem minnstu okkar
gildi og við viljum bera það.

1413
00:59:44,766 --> 00:59:47,090
Hvað viljum við bera saman það til?

1414
00:59:47,090 --> 00:59:48,730
Það er að fara að vera svona næsta einn, ekki satt?

1415
00:59:48,730 --> 00:59:53,200
Þannig viljum við k að frumstilla
til ég plús 1 til að byrja.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Og við viljum k í þessu tilfelli erum við
þegar hafa stærð geymt upp hér,

1418
01:00:02,800 --> 01:00:03,930
svo við getum bara notað stærð.

1419
01:00:03,930 --> 01:00:06,240
Size vera stærð fylkisins.

1420
01:00:06,240 --> 01:00:09,620
Og við viljum bara til
uppfæra k í hvert skipti.

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
Svo nú þurfum við að finna
minnsti þáttur hér.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Þannig að ef við iterate gegnum, við
langar að segja, ef array á k

1427
01:00:31,380 --> 01:00:37,080
er minna en minnstu value-- okkar
þetta er þar sem við erum í raun og veru

1428
01:00:37,080 --> 01:00:42,950
halda utan um hvað er
minnsti here--

1429
01:00:42,950 --> 01:00:47,740
þá viljum við að endurúthluta
hvað minnstu gildi okkar er.

1430
01:00:47,740 --> 01:00:50,645
>> Þetta þýðir að, ó, við erum
iterating gegnum hér.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Whatever gildi er hér er
ekki okkar minnstu hlutur.

1433
01:00:53,740 --> 01:00:54,448
Við viljum það ekki.

1434
01:00:54,448 --> 01:00:56,100
Við viljum breyta henni.

1435
01:00:56,100 --> 01:01:02,050
Þannig að ef við erum að reassigning það, hvað
þú heldur kannski að vera í þessum kóða hér?

1436
01:01:02,050 --> 01:01:04,160
Við viljum að endurúthluta
minnstu og stöðu.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Svo er það minnsta núna?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
Nemandi: Array k.

1441
01:01:09,130 --> 01:01:09,963
Umsjón: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Og hvað er staða núna?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Hvað er vísitala
Minnsta gildi okkar?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Það er bara k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Svo array k, k, passa þeir upp.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Þannig að við vildum að endurúthluta því.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Og svo eftir að við fannst minnstu okkar,
svo í lok þessa fyrir lykkju

1454
01:01:39,950 --> 01:01:45,100
hér höfum við fundið það minnsta okkar
gildi er, þannig að við skipta bara.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
Í þessu tilviki, eins og sagt okkar
Minnsta gildi er út hér.

1457
01:01:50,816 --> 01:01:51,940
Þetta er minnsta gildi okkar.

1458
01:01:51,940 --> 01:01:57,690
>> Við viljum bara að skipta henni hér, sem er
hvað sem skipta á virka neðst

1459
01:01:57,690 --> 01:02:01,270
gerði, sem við skrifuðum bara upp
saman í nokkrar mínútur síðan.

1460
01:02:01,270 --> 01:02:02,775
Svo það ætti að líta kunnuglegt.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Og þá mun það bara iterate
í gegnum þar til það nær alla leið

1463
01:02:08,030 --> 01:02:13,100
til enda, sem þýðir að þú
hafa núll þætti sem eru óflokkaðar

1464
01:02:13,100 --> 01:02:14,800
og allt annað hefur verið raðað.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Skynsamleg?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Smá meira concretely?

1469
01:02:19,280 --> 01:02:19,990
Kóðinn hjálp?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> Nemandi: Fyrir stærð, þú aldrei
virkilega skilgreina það eða breyta því,

1472
01:02:26,410 --> 01:02:27,340
hvernig virkar það vita?

1473
01:02:27,340 --> 01:02:32,380
>> Umsjón: Svo eitt til
taka upp hér er INT stærð.

1474
01:02:32,380 --> 01:02:35,680
Þannig að við erum að segja í þessu sort-- tagi
er fall í þessu case-- það

1475
01:02:35,680 --> 01:02:40,770
val tagi, það er liðin
með fallinu.

1476
01:02:40,770 --> 01:02:43,460
Þannig að ef það var ekki samþykkt
í, sem þú myndir gera eitthvað

1477
01:02:43,460 --> 01:02:47,840
eins og með lengd array
eða þú vildi iterate gegnum

1478
01:02:47,840 --> 01:02:49,390
að finna lengd.

1479
01:02:49,390 --> 01:02:52,680
En vegna þess að það er liðin
í, við getum bara notað það.

1480
01:02:52,680 --> 01:02:55,720
Þú tekur bara að notandinn
gaf þér gilt stærð sem

1481
01:02:55,720 --> 01:02:57,698
reyndar táknar
stærð array þinn.

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
>> Ef þú krakkar hafa allir vandræðum með þessum
eða vilja fleiri æfa erfðaskrá konar

1486
01:03:05,870 --> 01:03:08,050
á eigin spýtur, þú ættir
fara til study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Það er a tól.

1489
01:03:12,670 --> 01:03:15,040
Þeir hafa afgreiðslumaður sem
þú getur raunverulega skrifa.

1490
01:03:15,040 --> 01:03:16,180
Þeir gera sauðakóða.

1491
01:03:16,180 --> 01:03:19,310
Þeir hafa fleiri myndbönd og skyggnur
þar á meðal þær sem ég nota hér.

1492
01:03:19,310 --> 01:03:23,150
Svo ef þú ert enn að tilfinning a
lítið loðinn, reyna það út.

1493
01:03:23,150 --> 01:03:25,670
Eins og alltaf, koma tala við mig líka.

1494
01:03:25,670 --> 01:03:26,320
Spurning?

1495
01:03:26,320 --> 01:03:28,611
>> Nemandi: Ertu að segja að
stærð er áður skilgreint?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
Umsjón: Já.

1498
01:03:29,900 --> 01:03:35,570
Size er og áður var skilgreint upp
hér í aðgerðina yfirlýsingu.

1499
01:03:35,570 --> 01:03:39,060
Svo þú gera ráð fyrir að það er verið samþykkt í
af notanda, og fyrir sakir einfaldleika er,

1500
01:03:39,060 --> 01:03:41,896
við erum að fara að gera ráð fyrir að
notandi gaf okkur rétta stærð.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Svo er það val tegund.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Krakkar, ég veit að við erum að læra mikið í dag.

1505
01:03:47,640 --> 01:03:49,710
Það er þétt gögn fyrir kafla.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Svo með það, við erum að fara
að fara í innsetningu tagi.

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
Svo áður en að við þurfum að gera
Runtime greiningu okkar hér.

1511
01:04:06,100 --> 01:04:10,190
Svo í besta tilfelli,
veitt síðan ég sýndi þér

1512
01:04:10,190 --> 01:04:11,960
Taflan ég þegar
konar gaf henni.

1513
01:04:11,960 --> 01:04:15,430
En best að ræða afturkreistingur, hvað við höldum?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Allt flokkað.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N veldi.

1518
01:04:22,070 --> 01:04:24,780
Einhver hafa skýringu
fyrir því hvers vegna þú heldur?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> Nemandi: Þú ert að bera saman through--

1521
01:04:30,519 --> 01:04:31,268
Umsjón: Hægri.

1522
01:04:31,268 --> 01:04:32,540
Þú ert að bera saman í gegnum.

1523
01:04:32,540 --> 01:04:35,630
Á hverjum endurtekning, jafnvel þótt
við erum decrementing þetta með einn,

1524
01:04:35,630 --> 01:04:38,950
þú ert enn að leita í gegnum
allt til að finna minnstu einn.

1525
01:04:38,950 --> 01:04:42,390
Svo jafnvel ef minnstu gildi þitt
er hér í upphafi,

1526
01:04:42,390 --> 01:04:44,710
þú ert enn að bera það
gegn allt annað

1527
01:04:44,710 --> 01:04:46,550
að ganga úr skugga um að það er minnsti hlutur.

1528
01:04:46,550 --> 01:04:49,820
Svo þú munt á endanum að keyra í gegnum
bil n veldi sinnum.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Allt í lagi.

1531
01:04:51,590 --> 01:04:52,785
Og hvað er versta?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Einnig n veldi vegna þess að þú ert að fara
að vera að gera það sama aðferð.

1534
01:04:57,980 --> 01:05:01,670
Þannig að í þessu tilfelli, val
Raða eitthvað

1535
01:05:01,670 --> 01:05:04,010
sem við köllum líka ráð afturkreistingur.

1536
01:05:04,010 --> 01:05:07,400
Svo í öðrum, við vitum bara
efri og neðri mörk.

1537
01:05:07,400 --> 01:05:11,180
Það fer eftir því hvernig brjálaður okkar
listi er eða hvernig óflokkuðu það er,

1538
01:05:11,180 --> 01:05:15,350
þeir breytileg á milli n eða n öðru veldi.

1539
01:05:15,350 --> 01:05:16,550
Við vitum það ekki.

1540
01:05:16,550 --> 01:05:22,820
>> En vegna val raða hefur sömu
versta og besta tilfelli, sem segir okkur að

1541
01:05:22,820 --> 01:05:25,880
sama hvaða tegund af inntak við
hafa, hvort sem það er alveg

1542
01:05:25,880 --> 01:05:29,130
raðað eða alveg
andstæða raðað, það er

1543
01:05:29,130 --> 01:05:30,740
fara að taka sama magn af tíma.

1544
01:05:30,740 --> 01:05:33,760
Svo í því tilfelli, ef þú
muna frá borð okkar,

1545
01:05:33,760 --> 01:05:38,610
það hafði í raun gildi sem
þessir tveir tegund hafa ekki,

1546
01:05:38,610 --> 01:05:40,390
sem er gert ráð fyrir afturkreistingur.

1547
01:05:40,390 --> 01:05:43,350
Þannig að við vitum að þegar
hlaupum val konar,

1548
01:05:43,350 --> 01:05:45,380
það er ábyrgð að
keyra n veldi tíma.

1549
01:05:45,380 --> 01:05:46,630
Það er engin breytileiki þar.

1550
01:05:46,630 --> 01:05:47,630
Það er bara gert ráð fyrir.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Og aftur, ef þú vilt læra
meira, taka CS 124 í vor.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Allt í lagi.

1555
01:05:56,712 --> 01:05:57,545
Við höfum séð þetta einn.

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
Svo insertion sort.

1559
01:06:00,930 --> 01:06:03,330
Og ég er líklega að fara
að loga í gegnum þetta.

1560
01:06:03,330 --> 01:06:05,440
Ég mun ekki hafa þið kóða það.

1561
01:06:05,440 --> 01:06:06,580
Við verðum bara að ganga í gegnum það.

1562
01:06:06,580 --> 01:06:10,500
Svo er insertion sort góður
af svipað val tagi

1563
01:06:10,500 --> 01:06:14,460
í því að við höfum bæði óflokkuðu
og raðað hluta fylkisins.

1564
01:06:14,460 --> 01:06:20,260
>> En hvað er öðruvísi er að
eins og við förum í gegnum eitt af öðru,

1565
01:06:20,260 --> 01:06:24,210
við tökum bara hvað sem tala
er næst í óflokkaðs okkar,

1566
01:06:24,210 --> 01:06:28,507
og rétt tegund það
inn flokkaðs array okkar.

1567
01:06:28,507 --> 01:06:30,090
Það mun gera meira vit með dæmi.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Svo byrjar allt sem óflokkuðu,
bara eins og með val tagi.

1570
01:06:35,430 --> 01:06:38,740
Og við erum að fara að raða þessu í
Hækkandi röð eins og við höfum verið.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Svo á fyrsta okkar fara
við taka fyrsta gildi

1573
01:06:43,340 --> 01:06:46,700
og við segjum, OK, þú ert
nú á lista sjálfur.

1574
01:06:46,700 --> 01:06:49,150
>> Þar sem þú ert á lista
sjálfur, þú ert flokkuð.

1575
01:06:49,150 --> 01:06:52,460
Til hamingju fyrir að vera
Fyrsta þáttur í þessu fylki.

1576
01:06:52,460 --> 01:06:54,800
Þú ert nú þegar raðað allt á eigin spýtur.

1577
01:06:54,800 --> 01:06:58,900
Svo nú höfum við a raðað
og óflokkuðum array.

1578
01:06:58,900 --> 01:07:01,760
Svo nú erum við að taka fyrst.

1579
01:07:01,760 --> 01:07:05,600
Hvað gerist á milli hér
og hér er að við segjum,

1580
01:07:05,600 --> 01:07:08,890
OK, við erum að fara að horfa á
Fyrsta gildi óflokkaðs array okkar

1581
01:07:08,890 --> 01:07:13,270
og við erum að fara að inntak það í sinni
réttum stað í flokkaðs fylkisins.

1582
01:07:13,270 --> 01:07:21,460
>> Svo það sem við gerum er að við að taka 5 og
við segjum, OK, 5 er meira en 3,

1583
01:07:21,460 --> 01:07:24,630
svo við setja bara það rétt
til hægri á það.

1584
01:07:24,630 --> 01:07:25,130
Við erum góð.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Svo þá förum við á næsta einn okkar.

1587
01:07:28,420 --> 01:07:29,720
Og við tökum 2.

1588
01:07:29,720 --> 01:07:34,330
Við segjum, OK, 2 er minna
en 3, þannig að við vitum að það

1589
01:07:34,330 --> 01:07:36,220
þarf að vera á
framan á listanum okkar núna.

1590
01:07:36,220 --> 01:07:41,800
Svo það sem við gerum er að við ýta 3 og 5 niður
og við að færa 2 í það fyrsta rifa.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Þannig að við erum bara að setja það inn
réttum stað það ætti að vera.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Þá erum við að líta á okkar
næsta einn, og við segjum 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 er meiri en
allt í flokkaðs fylking okkar,

1596
01:07:53,620 --> 01:07:56,000
svo við tag bara það á til enda.

1597
01:07:56,000 --> 01:07:56,960
Og þá erum við að líta á 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 er minna en 6, það er minna
en 5 en það er meira en 3.

1600
01:08:03,020 --> 01:08:06,270
Þannig að við að setja bara það rétt inn
mitt á milli 3 og 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Svo til að gera það svolítið
aðeins meira steypu,

1603
01:08:10,530 --> 01:08:12,280
hér er góður af
hugmynd um hvað gerðist.

1604
01:08:12,280 --> 01:08:16,430
Svo fyrir hvert óflokkuðu frumefni, við
ákvarða hvar í flokkaðs hluta

1605
01:08:16,430 --> 01:08:17,090
það er.

1606
01:08:17,090 --> 01:08:20,680
>> Svo hafðu í huga að
raðað og óflokkaðar,

1607
01:08:20,680 --> 01:08:26,080
við verðum að fara í gegnum og mynd
út hvar það passar í flokkaðs fylkisins.

1608
01:08:26,080 --> 01:08:31,460
Og við setja það með því að færa
þættir til hægri það niður.

1609
01:08:31,460 --> 01:08:34,910
Og þá erum við að halda bara
iterating gegnum þar til við

1610
01:08:34,910 --> 01:08:39,270
hafa a fullkomlega raðað lista
þar óflokkuðu er nú núll

1611
01:08:39,270 --> 01:08:41,720
og raðað tekur upp
heild á listanum okkar.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Svo, aftur, til að gera hlutina enn
meira steypu, höfum við sauðakóða.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Svo í grundvallaratriðum fyrir i er
jafnt og 0 til n mínus 1,

1616
01:08:52,410 --> 01:08:54,790
það er bara lengd array okkar.

1617
01:08:54,790 --> 01:09:00,979
Við höfum sumir þáttur sem er jafn
fyrsta array eða fyrstu vísitölur.

1618
01:09:00,979 --> 01:09:03,200
Við setjum j jafnan við það.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Svo á meðan j er meiri en
núll og array, J mínus 1

1621
01:09:09,210 --> 01:09:11,660
er meiri en
þáttur, þannig að allt sem er að gera

1622
01:09:11,660 --> 01:09:17,479
er að tryggja að
J þitt raunverulega táknar

1623
01:09:17,479 --> 01:09:20,010
sem óflokkuðu hluta fylkisins.

1624
01:09:20,010 --> 01:09:30,745
>> Svo á meðan það er enn hluti
að flokka og j mínus einn is-- hvað

1625
01:09:30,745 --> 01:09:31,840
er þáttur hennar?

1626
01:09:31,840 --> 01:09:34,760
J var aldrei skilgreint hér.

1627
01:09:34,760 --> 01:09:35,677
Það er góður af pirrandi.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Engu að síður.

1630
01:09:36,689 --> 01:09:39,899
Svo J mínus 1, þú ert að stöðva
þátturinn fyrir það.

1631
01:09:39,899 --> 01:09:46,460
Þú ert að segja, OK, er þáttur
áður þar sem ég am-- skulum

1632
01:09:46,460 --> 01:09:47,540
reyndar draga þetta út.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Svo skulum segja að þetta sé
eins og á öðrum okkar fara.

1635
01:09:56,830 --> 01:09:59,525
Svo ég er að fara að vera jöfn
til 1, sem er hér.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Svo ég er að fara að vera jafnt og 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Þetta mundi vera 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Allt í lagi.

1642
01:10:16,750 --> 01:10:20,945
Svo þáttur okkar í þessu tilfelli
er að fara að vera jafn og 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Og við höfum einhverja j sem er
fara að vera jafnt og 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Ó, j er decrementing.

1647
01:10:30,971 --> 01:10:31,720
Það er það sem það er.

1648
01:10:31,720 --> 01:10:35,680
Svo er J jöfn i, svo hvað þetta er
segja er að eins og við halda áfram,

1649
01:10:35,680 --> 01:10:37,530
við erum bara að gera viss
að við erum ekki yfir

1650
01:10:37,530 --> 01:10:43,520
flokkun með þessum hætti þegar við erum að reyna
að setja hlutina inn raðað lista okkar.

1651
01:10:43,520 --> 01:10:49,850
>> Svo þegar j er jafnt og 1 í þessu tilfelli og
array J mínus one-- svo array J mínus 1

1652
01:10:49,850 --> 01:10:54,610
er 2 í þessu case-- ef það er
meiri en frumefni,

1653
01:10:54,610 --> 01:10:57,700
þá allt þetta er að gera
er að breytast það niður.

1654
01:10:57,700 --> 01:11:04,790
Þannig að í þessu tilfelli, array J mínus einn
væri array núll, sem er 2.

1655
01:11:04,790 --> 01:11:08,430
2 er ekki meiri en 4,
svo þetta er ekki keyrt.

1656
01:11:08,430 --> 01:11:11,460
Svo breyting ekki að fara niður.

1657
01:11:11,460 --> 01:11:18,790
Hvað þetta gerir hér er bara
færa raðað array niður.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
Í þessu tilviki, í raun, að við
gæti do-- skulum gera þetta 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Þannig að ef við erum að ganga í gegnum með
þetta dæmi, við erum nú hér.

1662
01:11:31,970 --> 01:11:32,740
Þetta er flokkað.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Þetta er óflokkuðum.

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
Svo er ég jafnt og 2, þannig
þáttur okkar er jafnt og 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Og j okkar er jafnt og 2.

1670
01:11:52,270 --> 01:12:00,620
Svo við horfir í gegnum og við
segja, OK, er array J mínus einn

1671
01:12:00,620 --> 01:12:03,470
meiri en frumefni
að við erum að horfa á?

1672
01:12:03,470 --> 01:12:05,540
Og svarið er já, ekki satt?

1673
01:12:05,540 --> 01:12:11,275
4 er meiri en 3 og j
er 2, þannig að þetta númer framkvæmd.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Svo nú hvað við gerum á fjölbreytta á
2, svo hérna, skipta við þá.

1676
01:12:18,550 --> 01:12:25,620
Þannig að við segjum bara, OK, array
á 2 er nú að fara að vera 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Og j er að fara til að jafna
J mínus 1, sem er 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Það er hræðilegt, en
þú krakkar fá hugmynd.

1681
01:12:37,200 --> 01:12:38,360
J er nú jafnt og 1.

1682
01:12:38,360 --> 01:12:44,360
Og array j er bara að fara að vera
jafn þáttur okkar sem var 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Ég þurrkast eitthvað sem ég ætti ekki að
hafa eða miswrote eitthvað,

1685
01:12:48,570 --> 01:12:49,910
en þú krakkar fá hugmynd.

1686
01:12:49,910 --> 01:12:50,640
>> Það að færa á n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Og þá ef þetta væri, myndi það lykkja
aftur og það myndi segja, OK, j er 1 núna.

1689
01:12:57,960 --> 01:13:00,665
Og array J mínus 1 er nú 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Er 2 minna en frumefni okkar?

1692
01:13:03,760 --> 01:13:04,540
Nei?

1693
01:13:04,540 --> 01:13:07,970
Það þýðir að við höfum
sett þennan þátt

1694
01:13:07,970 --> 01:13:10,110
í réttri blettur í flokkaðs array okkar.

1695
01:13:10,110 --> 01:13:14,400
Þá getum við tekið þetta og við segjum,
OK, raðað array okkar er hér.

1696
01:13:14,400 --> 01:13:19,940
Og það myndi taka þetta númer 6 og vera
eins, OK, er 6 minna en þetta númer?

1697
01:13:19,940 --> 01:13:20,480
Nei?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Við erum í lagi.

1700
01:13:22,680 --> 01:13:23,530
>> Gerðu það aftur.

1701
01:13:23,530 --> 01:13:24,740
Við segjum 7.

1702
01:13:24,740 --> 01:13:29,010
Er 7 minna en í lok
flokkaðs array okkar?

1703
01:13:29,010 --> 01:13:29,520
No.

1704
01:13:29,520 --> 01:13:30,430
Þannig að við erum í lagi.

1705
01:13:30,430 --> 01:13:32,760
Þannig að þetta myndi vera flokkaður.

1706
01:13:32,760 --> 01:13:38,610
Rauninni allt þetta
er það að segja taka

1707
01:13:38,610 --> 01:13:42,060
fyrsta þáttur í
óflokkaðs array þinn,

1708
01:13:42,060 --> 01:13:46,010
reikna út hvar það fer
í flokkaðs fylking þinni.

1709
01:13:46,010 --> 01:13:48,780
Og þetta tekur bara umönnun
skiptasamninga til að gera það.

1710
01:13:48,780 --> 01:13:51,300
Þú ert í rauninni bara að skipta
þar til það er í rétta staðnum.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Sjónræna mynd er að þú ert
færa allt niður með því að gera það.

1713
01:13:56,990 --> 01:13:59,420
>> Svo það er eins og hálf kúla tegund-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Kíkja rannsókn 50.

1716
01:14:03,420 --> 01:14:06,000
Ég mæli reyna
að kóða þetta á eigin spýtur.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Ef þú hefur einhverjar málefni eða ef þú vilt
sjá dæmi um kóða fyrir Innsetningarröðun,

1719
01:14:12,450 --> 01:14:13,750
vinsamlegast láttu mig vita.

1720
01:14:13,750 --> 01:14:14,500
Ég er alltaf í kring.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Svo versta tilfelli afturkreistingur
og besta tilfelli afturkreistingur.

1723
01:14:20,200 --> 01:14:30,700
Eins og þú sást strákur frá töflunni ég þegar
sýndi þér, það er bæði n veldi og n.

1724
01:14:30,700 --> 01:14:35,590
>> Svo góður að fara burt af því sem við ræddum
um með fyrri konar okkar, versta

1725
01:14:35,590 --> 01:14:38,760
ræða afturkreistingur er að ef
það er alveg óflokkað,

1726
01:14:38,760 --> 01:14:42,530
við verðum að bera allar þessar n sinnum.

1727
01:14:42,530 --> 01:14:47,020
Við gerum allt fullt af samanburði
því ef það er í öfugri röð,

1728
01:14:47,020 --> 01:14:50,360
við erum að fara að segja, OK, þetta
er það sama, þetta er gott,

1729
01:14:50,360 --> 01:14:54,650
og þetta verður að vera í samanburði
gegn þeirri fyrstu til að vera flutt til baka.

1730
01:14:54,650 --> 01:14:56,710
Og eins og við fá til
hala lok, við höfum

1731
01:14:56,710 --> 01:14:59,440
að bera saman, bera saman, og
bera saman við allt.

1732
01:14:59,440 --> 01:15:03,030
>> Svo það endar að vera
bil n veldi.

1733
01:15:03,030 --> 01:15:09,510
Ef það er rétt þá er
segja, OK, 2, þú ert góður.

1734
01:15:09,510 --> 01:15:11,330
3, ætlar þú miðað við 2.

1735
01:15:11,330 --> 01:15:12,310
Þú ert góður.

1736
01:15:12,310 --> 01:15:14,150
4, bera bara á skottið.

1737
01:15:14,150 --> 01:15:14,990
Þú ert góður.

1738
01:15:14,990 --> 01:15:17,140
6, bera saman við skottið, þú ert fínn.

1739
01:15:17,140 --> 01:15:20,870
Svo fyrir hvern staðnum ef það er þegar
raðað, ert þú að gera einn samanburð.

1740
01:15:20,870 --> 01:15:22,320
Svo er það bara n.

1741
01:15:22,320 --> 01:15:26,840
Og vegna þess að við höfum besta tilfelli afturkreistingur
n og versta afturkreistingur af n

1742
01:15:26,840 --> 01:15:28,680
veldi, höfum við enga vænta afturkreistingur.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Það veltur bara á
óreiðu af listanum okkar þar.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Og aftur, annar
línurit og annað borð.

1747
01:15:39,530 --> 01:15:41,170
Svo mismunandi milli konar.

1748
01:15:41,170 --> 01:15:44,180
Ég ætla bara að fara að gola í gegnum, ég
finnst eins og við höfum talað mikið

1749
01:15:44,180 --> 01:15:46,570
um hvernig þeir allskonar
af mismunandi og tengja saman.

1750
01:15:46,570 --> 01:15:50,564
Svo Mergesort er síðasta einn
Ég skal ól ykkur með.

1751
01:15:50,564 --> 01:15:52,105
Við höfum nokkuð litríka mynd.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Svo sameinast tegund er endurkvæma reiknirit.

1754
01:15:56,040 --> 01:15:59,910
Svo þú krakkar vita hvað
a endurkvæma virka er?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Einhver vilja til segja?

1757
01:16:03,320 --> 01:16:04,739
Þú vilt reyna?

1758
01:16:04,739 --> 01:16:07,280
Svo er a endurkvæma virka bara
fall sem kallar sig.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Svo ef þú krakkar eru kunnugir
með Fibonacci röð,

1761
01:16:11,590 --> 01:16:15,670
sem er talið endurkvæma vegna
þú tekur síðustu tveimur

1762
01:16:15,670 --> 01:16:17,530
og bæta þeim saman
að fá næsta einn.

1763
01:16:17,530 --> 01:16:21,440
Svo endurkvæma, held ég alltaf
af endurkvæmni sem eins spíral

1764
01:16:21,440 --> 01:16:24,430
svo þú ert eins og ört vaxandi niður í það.

1765
01:16:24,430 --> 01:16:27,150
En það er bara fall
sem kallar sig.

1766
01:16:27,150 --> 01:16:32,660
>> Og reyndar, í raun fljótt ég
getur sýnt þér hvað það lítur út.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Svo endurkvæma hér, ef við lítum, þetta er
endurkvæma leiðin að summa yfir fylki.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Svo allt sem við gerum er
við höfum summa virka

1771
01:16:47,880 --> 01:16:52,210
fjárhæð sem tekur stærð og fjölda.

1772
01:16:52,210 --> 01:16:55,210
Og ef þú tekur eftir, stærð
skjárínn telur niður um einn tíma.

1773
01:16:55,210 --> 01:17:00,365
Og allt það gerir er ef X er jafnt
zero-- svo ef stærð fylkisins

1774
01:17:00,365 --> 01:17:02,710
er jafnt zero-- það skilar núll.

1775
01:17:02,710 --> 01:17:10,440
>> Annars er það fjárhæðir þetta
síðasta þáttur í fylkinu,

1776
01:17:10,440 --> 01:17:14,790
og þá tekur summu af
restin af fylkisins.

1777
01:17:14,790 --> 01:17:17,555
Svo það er bara að brjóta það niður
í smærri og smærri vandamál.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Long saga stutt, endurkvæmni,
fall sem kallar sig.

1780
01:17:21,890 --> 01:17:25,740
Ef það er allt sem þú fékk út úr þessu,
það er það a endurkvæma virka er.

1781
01:17:25,740 --> 01:17:29,870
Ef þú tekur 51, þú vilja fá mjög,
mjög ánægð með endurkvæmni.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Það er mjög svalt.

1784
01:17:32,370 --> 01:17:34,660
Það vit á eins
03:00 eitt kvöldið út.

1785
01:17:34,660 --> 01:17:37,900
Og ég var eins og, af hverju
hef ég aldrei notað þetta?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Svo fyrir Mergesort, grundvallaratriðum
hvað það er að fara að gera er að það er

1788
01:17:42,430 --> 01:17:45,620
að fara að brjóta það niður og brjóta það
niður þar til það er bara single þættir.

1789
01:17:45,620 --> 01:17:47,570
The einn þættir eru auðvelt að raða.

1790
01:17:47,570 --> 01:17:48,070
Við sjáum það.

1791
01:17:48,070 --> 01:17:50,760
Ef þú ert einn þáttur, það er
þegar talið flokkuð.

1792
01:17:50,760 --> 01:17:53,800
Svo á inntak n þáttum,
ef n er minna en 2,

1793
01:17:53,800 --> 01:17:58,120
bara aftur því það þýðir að
það er annað hvort 0 eða 1 eins og við höfum séð.

1794
01:17:58,120 --> 01:18:00,050
Þeir teljast flokkuð þættir.

1795
01:18:00,050 --> 01:18:02,170
>> Annars brjóta það í tvennt.

1796
01:18:02,170 --> 01:18:06,336
Raða fyrri hluta, raða annað
helmingur, og þá sameinast þeim saman.

1797
01:18:06,336 --> 01:18:07,460
Hvers vegna það er kallað Mergesort.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Þannig að við höfum hér við munum raða þeim.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Svo við höldum með þeim
þar til array stærð er 1.

1802
01:18:17,210 --> 01:18:20,790
Svo þegar það er 1, aftur við bara
því þetta er Raðað array,

1803
01:18:20,790 --> 01:18:23,940
og þetta er Raðað array, og það er
a Raðað array, erum við öll flokkuð.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Svo þá hvað við gerum er að við
byrja samruna þeim saman.

1806
01:18:29,420 --> 01:18:31,820
>> Svo eins og þú getur
hugsa um sameiningu er

1807
01:18:31,820 --> 01:18:36,240
þú fjarlægir bara minni
fjöldi hver af sub fylki

1808
01:18:36,240 --> 01:18:38,330
og bara auka við það að skapast fylkisins.

1809
01:18:38,330 --> 01:18:44,290
Svo ef þú lítur hér, þegar við höfum
Þetta setur við höfum 4, 6, og 1.

1810
01:18:44,290 --> 01:18:47,280
Þegar við viljum sameina þetta,
við líta á þessum fyrstu tveimur

1811
01:18:47,280 --> 01:18:50,730
og við segjum, OK, 1 er minni,
það fer að framan.

1812
01:18:50,730 --> 01:18:54,330
4 og 6, það er ekkert til að bera saman
það til, bara merkja það á til enda.

1813
01:18:54,330 --> 01:18:58,020
>> Þegar við sameina þessar tvær, við bara
taka minni einn af þessum tveimur,

1814
01:18:58,020 --> 01:18:59,310
svo það er 1.

1815
01:18:59,310 --> 01:19:01,690
Og nú erum við að taka
minni af þessum tveimur, SO 2.

1816
01:19:01,690 --> 01:19:03,330
Minna af þessum tveimur, 3.

1817
01:19:03,330 --> 01:19:06,260
Minna af þessum tveimur, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Svo þú ert bara að toga á þessum.

1819
01:19:08,630 --> 01:19:11,210
Og vegna þess að þeir eru búnir
verið raðað áður,

1820
01:19:11,210 --> 01:19:14,300
þú ert bara einn
samanburður í hvert sinn þar.

1821
01:19:14,300 --> 01:19:19,610
Svo fleiri kóða hér, bara framsetning.

1822
01:19:19,610 --> 01:19:24,410
Svo þú byrjar á miðju og
þú raða vinstri og hægri

1823
01:19:24,410 --> 01:19:26,180
og þá sameinast bara þá.

1824
01:19:26,180 --> 01:19:30,080
>> Og við höfum ekki númerið
fyrir steypa hérna.

1825
01:19:30,080 --> 01:19:34,110
En, aftur, ef þú ferð á
rannsókn 50, það verður þar.

1826
01:19:34,110 --> 01:19:36,860
Annars koma að tala við mig
Ef þú ert enn að rugla.

1827
01:19:36,860 --> 01:19:42,340
Svo kaldur hlutur hér er að besta tilfelli,
versta tilfelli, og gert ráð fyrir afturkreistingur

1828
01:19:42,340 --> 01:19:46,250
eru allir í log n, sem
er miklu betra en við höfum

1829
01:19:46,250 --> 01:19:48,000
séð fyrir afganginn af tegund okkar.

1830
01:19:48,000 --> 01:19:51,840
Við höfum séð n veldi
og það sem við raunverulega

1831
01:19:51,840 --> 01:19:54,380
fá hér er n log n, sem er frábært.

1832
01:19:54,380 --> 01:19:55,830
>> Horfðu á hversu mikið betur sem er.

1833
01:19:55,830 --> 01:19:56,780
Slík ágætur bugða.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Svo mun skilvirkari.

1836
01:20:00,120 --> 01:20:03,510
Ef þú getur alltaf, nota Mergesort.

1837
01:20:03,510 --> 01:20:04,810
Það mun spara þér tíma.

1838
01:20:04,810 --> 01:20:07,670
Þá aftur, eins og ég sagði, ef
þú ert niður í þennan litla svæði,

1839
01:20:07,670 --> 01:20:09,480
það þýðir ekki að gera það
mikið af a mismunur.

1840
01:20:09,480 --> 01:20:11,360
Þú færð allt að þúsund
og þúsundir af aðföngum,

1841
01:20:11,360 --> 01:20:13,318
þú vilt örugglega
skilvirkari reiknirit.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Og aftur, kæri borðið okkar af öllu
tegund sem þú krakkar lært í dag.

1844
01:20:19,400 --> 01:20:21,157
>> Þannig að ég veit að það hefur verið þétt dag.

1845
01:20:21,157 --> 01:20:23,490
Þetta er ekki endilega að fara
til að hjálpa þér með pset þinn.

1846
01:20:23,490 --> 01:20:28,250
En ég vil bara að gera höfnun
þessi hluti er ekki bara um psets.

1847
01:20:28,250 --> 01:20:31,240
Allt þetta efni er sanngjörn
leikur fyrir midterms þínum.

1848
01:20:31,240 --> 01:20:35,430
Og einnig ef þú halda áfram á CS,
þetta eru virkilega mikilvæg grundvallaratriði

1849
01:20:35,430 --> 01:20:37,870
að þú myndir þurfa að vita.

1850
01:20:37,870 --> 01:20:41,700
Svo nokkrum dögum verður
lítið meira pset hjálp,

1851
01:20:41,700 --> 01:20:44,600
en sumir vikur verða
miklu meira raunverulegt innihald

1852
01:20:44,600 --> 01:20:46,600
sem geta ekki virðast frábær
gagnlegt fyrir þig núna,

1853
01:20:46,600 --> 01:20:51,215
en ég lofa ef þú heldur áfram
á verður mjög, mjög gagnlegt.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Svo það er það fyrir hluta.

1856
01:20:54,250 --> 01:20:55,250
Niður á vírinn.

1857
01:20:55,250 --> 01:20:56,570
Ég gerði það innan einnar mínútu.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
En þar sem þú ferð.

1860
01:20:58,970 --> 01:21:01,240
Og ég mun hafa kleinuhringir eða sælgæti.

1861
01:21:01,240 --> 01:21:03,464
Er einhver með ofnæmi
eitthvað, við the vegur?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Egg og mjólk.

1864
01:21:05,890 --> 01:21:08,120
Svo kleinuhringir eru ekki?

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
Allt í lagi.

1868
01:21:10,770 --> 01:21:12,120
Súkkulaði nei?

1869
01:21:12,120 --> 01:21:12,620
Gylltu.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts eru góðar.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Við erum að fara að hafa
Gylltu næstu viku þá.

1874
01:21:17,045 --> 01:21:18,240
Það er það sem ég næ.

1875
01:21:18,240 --> 01:21:19,690
Þú krakkar hafa a mikill viku.

1876
01:21:19,690 --> 01:21:20,460
Lesa sérstakur þína.

1877
01:21:20,460 --> 01:21:22,130
>> Láttu mig vita ef þú hefur einhverjar spurningar.

1878
01:21:22,130 --> 01:21:25,300
Pset tvær einkunna skal
út til þín frá fimmtudag.

1879
01:21:25,300 --> 01:21:28,320
Ef þú hefur einhverjar spurningar
um hvernig ég farið eitthvað

1880
01:21:28,320 --> 01:21:32,250
eða hvers vegna ég farið eitthvað og ég
gerði, vinsamlegast sendu mér tölvupóst, koma tala við mig.

1881
01:21:32,250 --> 01:21:34,210
Ég er svolítið brjálaður á þessu
viku, en ég lofa

1882
01:21:34,210 --> 01:21:36,340
Ég mun samt svara innan 24 klst.

1883
01:21:36,340 --> 01:21:38,240
Svo hafa a mikill viku, allir.

1884
01:21:38,240 --> 01:21:40,090
Gangi þér vel á pset þinni.

1885
01:21:40,090 --> 01:21:41,248