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

2
00:00:00,488 --> 00:00:10,800
>> [Muzikavimo]

3
00:00:10,800 --> 00:00:13,500
Davidas Malan: Gerai.

4
00:00:13,500 --> 00:00:14,670
Gerai, pasveikinti atgal.

5
00:00:14,670 --> 00:00:18,120
Taigi tai yra 4 savaitė, pradžia
jo, jau.

6
00:00:18,120 --> 00:00:21,320
Ir jums priminti, kad praėjusią savaitę, mes įdėti
kodą skirta tik šiek tiek

7
00:00:21,320 --> 00:00:24,240
ir mes pradėjome kalbėti šiek tiek daugiau
aukšto lygio, apie tokius dalykus kaip

8
00:00:24,240 --> 00:00:28,130
paieškos ir rūšiavimo, kuris nors
šiek tiek paprastų idėjų, yra

9
00:00:28,130 --> 00:00:31,840
atstovas problemų klasei
jūs pradėsite spręsti ypač

10
00:00:31,840 --> 00:00:34,820
kaip jums pradėti galvoti apie galutinį
projektai ir įdomių sprendimų jūs

11
00:00:34,820 --> 00:00:36,760
gali tekti realaus pasaulio problemas.

12
00:00:36,760 --> 00:00:39,490
Dabar burbulas tarsi buvo vienas iš paprasčiausių
tokie algoritmai, ir tai

13
00:00:39,490 --> 00:00:42,900
dirbo turėdami šiuos mažus numerius
sąraše arba masyvo rūšies

14
00:00:42,900 --> 00:00:46,530
burbulas savo kelią į viršų, ir
didelis skaičius perkelti savo kelią žemyn

15
00:00:46,530 --> 00:00:47,930
Šio sąrašo pabaigoje.

16
00:00:47,930 --> 00:00:50,650
>> Ir priminti, kad mes galime vizualizuoti
burbulas rūšiuoti mažai

17
00:00:50,650 --> 00:00:52,310
kažkas panašaus į tai.

18
00:00:52,310 --> 00:00:53,640
Taigi leiskite man eiti į priekį ir spustelėkite Pradėti.

19
00:00:53,640 --> 00:00:55,350
Aš iš anksto pasirinkti burbulas rūšiuoti.

20
00:00:55,350 --> 00:00:58,920
Ir jei jūs prisimenate, kad aukštesni mėlyna
linijos sudaro didelis skaičius, mažas

21
00:00:58,920 --> 00:01:03,300
mėlynos linijos sudaro nedidelis skaičius, kaip
mes pereiti per tai vėl ir vėl, ir

22
00:01:03,300 --> 00:01:07,680
vėl, lyginant dvi juostas viena šalia
kitas raudonai, mes ketiname apsikeitimo

23
00:01:07,680 --> 00:01:11,010
didžiausias ir mažiausias jei
jie yra ne iš eilės.

24
00:01:11,010 --> 00:01:14,150
>> Taigi, tai bus eiti ir eiti ir eiti
įjungtas, ir jūs pamatysite, kad didesnis

25
00:01:14,150 --> 00:01:16,700
elementai yra padaryti savo kelią į
sugebėjimus ir mažesni elementai

26
00:01:16,700 --> 00:01:17,900
padaryti savo kelią į kairę.

27
00:01:17,900 --> 00:01:21,380
Bet mes pradėjo kiekybiškai
efektyvumas,

28
00:01:21,380 --> 00:01:22,970
kokybė šį algoritmą.

29
00:01:22,970 --> 00:01:25,200
Ir mes pasakėme, kad blogiausia
atveju šis algoritmas buvo

30
00:01:25,200 --> 00:01:27,940
maždaug kiek žingsnių?

31
00:01:27,940 --> 00:01:28,980
>> Taigi n kvadratu.

32
00:01:28,980 --> 00:01:30,402
Ir tai, kas buvo n?

33
00:01:30,402 --> 00:01:31,650
>> Auditorija: Elementų skaičius.

34
00:01:31,650 --> 00:01:32,790
>> Davidas Malan: Taigi n buvo
skaičius elementų.

35
00:01:32,790 --> 00:01:33,730
Ir taip mes padarysime tai dažnai.

36
00:01:33,730 --> 00:01:36,650
Bet kuriuo metu mes norime kalbėti apie dydį
problema arba dydžio

37
00:01:36,650 --> 00:01:39,140
įėjimas, arba kiek laiko užtrunka
gaminti produkciją, mes tiesiog

38
00:01:39,140 --> 00:01:41,610
apibendrintas kokia
indėlis yra kaip n.

39
00:01:41,610 --> 00:01:45,970
Taigi atgal į savaitę 0, skaičius puslapiai
telefonų knygoje buvo n.

40
00:01:45,970 --> 00:01:47,550
Studentų skaičius
patalpoje buvo n.

41
00:01:47,550 --> 00:01:49,630
Taigi čia taip pat, mes po
kad modelis.

42
00:01:49,630 --> 00:01:52,800
>> Dabar n kvadratu ne itin
greitai, todėl mes bandėme padaryti geriau.

43
00:01:52,800 --> 00:01:55,970
Ir taip mes pažvelgė porą
kiti algoritmai, tarp kurių

44
00:01:55,970 --> 00:01:57,690
buvo pasirinkimas rūšiuoti.

45
00:01:57,690 --> 00:01:59,180
Taigi atranka tarsi buvo
šiek tiek kitoks.

46
00:01:59,180 --> 00:02:03,130
Tai buvo beveik paprasčiau, drįstu pasakyti,
kai aš pradėjau prie pradžios

47
00:02:03,130 --> 00:02:06,740
sąrašas iš mūsų savanorių, ir aš tiesiog dar kartą
ir vėl ir vėl išgyveno

48
00:02:06,740 --> 00:02:10,060
sąrašas, skynimas iš mažiausių
elementas metu ir išleisti jį arba

49
00:02:10,060 --> 00:02:13,040
ją prie sąrašo pradžioje.

50
00:02:13,040 --> 00:02:16,410
>> Tačiau tai taip pat, kai mes pradėjome galvoti
per matematikos ir didesnio

51
00:02:16,410 --> 00:02:19,860
paveikslėlį, pagalvojau apie tai, kiek kartų
Aš buvau ketinate pirmyn ir atgal ir atgal

52
00:02:19,860 --> 00:02:24,090
ir atgal, mes pasakėme, blogiausiu atveju,
pasirinkimas rūšiuoti, taip pat buvo ką?

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

54
00:02:24,960 --> 00:02:27,490
Dabar realiame pasaulyje, ji gali
iš tikrųjų šiek tiek greičiau.

55
00:02:27,490 --> 00:02:30,620
Nes vėl, aš neturėjau išlaikyti
atsitraukia kartą aš surūšiuoti

56
00:02:30,620 --> 00:02:31,880
smulkiausi elementai.

57
00:02:31,880 --> 00:02:35,090
Bet jei mes galvojame apie labai didelis n ir
jei tarsi daryti iš matematikos kaip

58
00:02:35,090 --> 00:02:39,170
Aš ant lentos, su n kvadratu
atėmus kažkas, visa kita

59
00:02:39,170 --> 00:02:41,850
be to, n kvadratu, kartą n
bus tikrai didelis, nėra

60
00:02:41,850 --> 00:02:42,850
tikrai nesvarbu kiek.

61
00:02:42,850 --> 00:02:45,470
Taigi, kaip kompiuterių specialistų, mes rūšiuoti
užmerkti akis į mažesnius

62
00:02:45,470 --> 00:02:49,220
veiksniai ir sutelkti dėmesį tik į veiksnys
išraiška, kuri ketina padaryti

63
00:02:49,220 --> 00:02:50,330
Didžiausias skirtumas.

64
00:02:50,330 --> 00:02:52,840
>> Na, galiausiai, mes pažvelgė
ne įterpimo rūšiuoti.

65
00:02:52,840 --> 00:02:56,620
Ir tai nuotaika buvo panaši į, bet
o ne eiti per keletą kartų ir

66
00:02:56,620 --> 00:03:01,250
pasirinkite mažiausią elementą vieną
kartą, aš vietoj paėmė ranką, kad aš

67
00:03:01,250 --> 00:03:04,070
buvo nagrinėjamas, ir aš nusprendžiau, visi
Gerai, jūs priklausote čia.

68
00:03:04,070 --> 00:03:06,160
Tada aš persikėlė į kitą elementą
ir nusprendė, kad jis arba

69
00:03:06,160 --> 00:03:07,470
ji priklausė čia.

70
00:03:07,470 --> 00:03:08,810
Ir tada aš persikėlė ir.

71
00:03:08,810 --> 00:03:11,780
Ir aš gali tam, pakeliui,
perkelti šie vaikinai siekiant

72
00:03:11,780 --> 00:03:13,030
padaryti vietos jiems.

73
00:03:13,030 --> 00:03:16,880
Taigi, tai buvo tarsi psichikos atstatymo
Atrankos rūšiuoti, kad mes

74
00:03:16,880 --> 00:03:18,630
vadinama įterpimo rūšiuoti.

75
00:03:18,630 --> 00:03:20,810
>> Taigi šios temos pasitaiko
realiame pasaulyje.

76
00:03:20,810 --> 00:03:23,640
Vos prieš kelerius metus, kai tam tikros
senatorius buvo paleisti į prezidentus,

77
00:03:23,640 --> 00:03:27,160
Ericas Schmidtas, tuo metu, kai generalinis direktorius
"Google", iš tikrųjų turėjo galimybę

78
00:03:27,160 --> 00:03:28,040
apklausti jį.

79
00:03:28,040 --> 00:03:32,010
Ir mes manome, kad mes norime pasidalinti šia YouTube
klipas jums čia, jei galėtume riesti

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

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO PLAYBACK]

82
00:03:39,360 --> 00:03:44,620
>> -Dabar, senatorius, jūs čia "Google"
ir man patinka galvoti apie pirmininkavimo

83
00:03:44,620 --> 00:03:46,042
kaip darbo interviu.

84
00:03:46,042 --> 00:03:47,770
>> [Juokas]

85
00:03:47,770 --> 00:03:50,800
>> -Dabar tai sunku gauti
kaip prezidentas darbas.

86
00:03:50,800 --> 00:03:52,480
Ir jūs ketinate per
sąstingis dabar.

87
00:03:52,480 --> 00:03:54,330
Taip pat sunku gauti "Google" darbą.

88
00:03:54,330 --> 00:03:59,610
Mes turime klausimus ir mes klausiame
mūsų kandidatai klausimai.

89
00:03:59,610 --> 00:04:02,250
Ir tai vienas iš Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Juokas]

91
00:04:05,325 --> 00:04:06,400
-Vaikinai manau, kad aš juokauju?

92
00:04:06,400 --> 00:04:08,750
Tai čia.

93
00:04:08,750 --> 00:04:12,110
Kas yra efektyviausias būdas
rūšiuoti milijono dviejų bitų sveikųjų skaičių?

94
00:04:12,110 --> 00:04:15,810
>> [Juokas]

95
00:04:15,810 --> 00:04:18,260
>> -Na, na -

96
00:04:18,260 --> 00:04:19,029
>> -I 'm sorry.

97
00:04:19,029 --> 00:04:19,745
Gal mes turėtume -

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

99
00:04:21,000 --> 00:04:21,470
>> -Tai ne -

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

101
00:04:22,185 --> 00:04:25,328
>> -Manau, kad burbulas tarsi būtų
būti neteisingas kelias.

102
00:04:25,328 --> 00:04:26,792
>> [Juokas]

103
00:04:26,792 --> 00:04:28,510
>> [Giedras ir plojimai]

104
00:04:28,510 --> 00:04:31,211
>> -Nagi, kas jam šį?

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

106
00:04:32,155 --> 00:04:33,350
>> [PABAIGA VIDEO PLAYBACK]

107
00:04:33,350 --> 00:04:35,070
>> Davidas Malan: Taigi jūs turite jį.

108
00:04:35,070 --> 00:04:39,600
Taigi mes pradėjome kiekybiškai tai veikia
kartų, taip sakant, su kažkuo

109
00:04:39,600 --> 00:04:43,480
vadinamas asymptotic žymėjimas, kuris yra
tik nuoroda į mūsų rūšies tekinimo

110
00:04:43,480 --> 00:04:47,420
aklas akis tiems mažesnių veiksnių ir
tik žiūri į važiavimo laikas,

111
00:04:47,420 --> 00:04:51,250
Šių algoritmų efektyvumą,
kaip n bus tikrai didelis laikui bėgant.

112
00:04:51,250 --> 00:04:55,110
Ir taip mes pristatėme didelis O. ir didelis O
atstovaujama kažkas, kad mes manome, kad

113
00:04:55,110 --> 00:04:57,000
AS viršutinė riba.

114
00:04:57,000 --> 00:04:59,570
Ir iš tiesų, Barry, mes galime sumažinti
nei mikrofono truputį?

115
00:04:59,570 --> 00:05:01,040
>> Manėme, kad tai yra viršutinė riba.

116
00:05:01,040 --> 00:05:04,710
Taigi didelis O nuo n kvadratu, reiškia, kad
Blogiausiu atveju, kažkas panašaus

117
00:05:04,710 --> 00:05:07,780
pasirinkimas rūšiuoti užtruktų
n kvadratu veiksmus.

118
00:05:07,780 --> 00:05:10,310
Ar kažkas panašaus įterpimo rūšiuoti
būtų n kvadratu žingsniai.

119
00:05:10,310 --> 00:05:15,150
Dabar kažką panašaus budas
rūšiuoti, kas blogiausiu atveju?

120
00:05:15,150 --> 00:05:18,200
Atsižvelgiant į tai, masyvas, kas blogiausia
galimas scenarijus, kad jūs galite rasti

121
00:05:18,200 --> 00:05:20,650
sau susiduria su?

122
00:05:20,650 --> 00:05:21,860
>> Tai visiškai atgal, tiesa?

123
00:05:21,860 --> 00:05:24,530
Nes jei tai visiškai atgal,
jūs turite padaryti visai daug darbo.

124
00:05:24,530 --> 00:05:26,420
Nes jei jūs esate visiškai atgal,
jūs ketinate rasti

125
00:05:26,420 --> 00:05:28,840
didžiausias elementas čia, nors
ji priklauso ten.

126
00:05:28,840 --> 00:05:31,140
Taigi jūs ketinate pasakyti, gerai, bent
tai laiko momentas, jūs priklausote čia

127
00:05:31,140 --> 00:05:32,310
todėl jūs palikti jį ramybėje.

128
00:05:32,310 --> 00:05:35,425
>> Tada jūs suprasite, oh, velnias, ir aš turiu
perkelti šį šiek tiek mažesnis elementas

129
00:05:35,425 --> 00:05:36,470
jus į kairę.

130
00:05:36,470 --> 00:05:38,770
Tada aš turiu daryti, kad vėl
ir vėl ir vėl.

131
00:05:38,770 --> 00:05:41,410
Ir jei aš vaikščiojo pirmyn ir atgal, jūs
būtų tarsi jaučia veikimą

132
00:05:41,410 --> 00:05:45,540
kad algoritmas, nes nuolat esu
shuffling visi kiti žemyn

133
00:05:45,540 --> 00:05:46,510
masyvas, kad paliktume jį.

134
00:05:46,510 --> 00:05:47,750
Štai blogiausiu atveju.

135
00:05:47,750 --> 00:05:48,570
>> Priešingai -

136
00:05:48,570 --> 00:05:50,320
ir tai buvo Įspūdingos filmą paskutinį kartą -

137
00:05:50,320 --> 00:05:54,065
sakėme, kad įterpimo rūšiuoti
buvo, ką Omega?

138
00:05:54,065 --> 00:05:57,530
Kas geriausiu atveju veikia
laikas įterpimo rūšiuoti?

139
00:05:57,530 --> 00:05:58,520
Taigi, tai tikrai n.

140
00:05:58,520 --> 00:06:00,980
Tai buvo tuščias, kad mes palikome
ant lentos paskutinį kartą.

141
00:06:00,980 --> 00:06:03,160
>> Ir tai omega n, nes kodėl?

142
00:06:03,160 --> 00:06:06,630
Na, labai geriausiu atveju kas
įterpimo rūšiuoti bus įteiktas?

143
00:06:06,630 --> 00:06:09,830
Na, sąrašas, kurį visiškai rūšiuojami
jau minimalus darbo padaryti.

144
00:06:09,830 --> 00:06:12,460
Bet kas, tvarkingas apie įterpimo rūšiuoti
yra tas, kad jis prasideda čia ir

145
00:06:12,460 --> 00:06:15,340
nusprendžia, oi, jūs numeris
viena, jūs priklausote čia.

146
00:06:15,340 --> 00:06:16,970
O, kas laimės.

147
00:06:16,970 --> 00:06:17,740
>> Jūs numeris du.

148
00:06:17,740 --> 00:06:19,030
Jūs taip pat priklauso šiai.

149
00:06:19,030 --> 00:06:21,010
Numeris trys, dar geriau,
Jūs priklausote čia.

150
00:06:21,010 --> 00:06:25,210
Kai tik jis gauna į pabaigos
sąrašas, už įterpimo Rūšiuoti anketa Pseudocode

151
00:06:25,210 --> 00:06:28,010
kad mes vaikščioti per žodžiu
paskutinį kartą, tai daroma.

152
00:06:28,010 --> 00:06:32,790
Bet pasirinkimas rūšiuoti, priešingai,
nuolat tai daryti, ką?

153
00:06:32,790 --> 00:06:35,260
>> Nuolat vyksta per sąrašą
vėl ir vėl ir vėl.

154
00:06:35,260 --> 00:06:39,160
Kadangi pagrindinė įžvalga buvo tik
kai jūs pažvelgė visą kelią iki

155
00:06:39,160 --> 00:06:42,500
pabaigoje sąrašo galite būti tikri,
kad elementas pasirinkote buvo

156
00:06:42,500 --> 00:06:45,560
Iš tiesų šiuo metu mažiausias elementas.

157
00:06:45,560 --> 00:06:48,920
Taigi tai skiriasi psichikos modeliai pabaiga
iki duoda keletą labai realaus pasaulio

158
00:06:48,920 --> 00:06:53,130
skirtumai mums, taip pat šių
teoriniai asimptotiniai skirtumai.

159
00:06:53,130 --> 00:06:56,910
>> Taigi tiesiog Priminti tada, Didelės O n
langeliais, mes matėme keletą tokių

160
00:06:56,910 --> 00:06:58,350
algoritmai iki šiol.

161
00:06:58,350 --> 00:06:59,580
Didelės O n?

162
00:06:59,580 --> 00:07:02,870
Kas yra algoritmas, kuris galėtų
būti laikomas didelis O n?

163
00:07:02,870 --> 00:07:06,930
Blogiausiu atveju, ji trunka
linijinis pakopų skaičius.

164
00:07:06,930 --> 00:07:07,810
>> Gerai, linijiniai paieška.

165
00:07:07,810 --> 00:07:10,470
O blogiausiu atveju, jei yra
elementas jūs ieškote, kai

166
00:07:10,470 --> 00:07:12,950
taikant linijinį ieškoti?

167
00:07:12,950 --> 00:07:14,680
>> Gerai, blogiausiu atveju,
tai net ne ten.

168
00:07:14,680 --> 00:07:17,000
Arba antrąja blogiausiu atveju, tai
visi galų gale būdas, kuris yra

169
00:07:17,000 --> 00:07:18,880
plius ar minus-vienas žingsnis skirtumas.

170
00:07:18,880 --> 00:07:21,180
Tad dienos pabaigoje,
mes galime pasakyti, kad linijinė.

171
00:07:21,180 --> 00:07:23,910
Didelės O n būtų tiesinis paieška,
nes blogiausiu atveju,

172
00:07:23,910 --> 00:07:26,610
elementas net ne ten, ar tai
visi pabaigoje būdas.

173
00:07:26,610 --> 00:07:29,370
>> Na, didelis O iš žurnalo n.

174
00:07:29,370 --> 00:07:32,760
Mes ne kalbėti labai išsamiai apie
tai, bet mes matėme anksčiau.

175
00:07:32,760 --> 00:07:36,840
Ką veikia vadinamasis logaritminė
laikas, blogiausiu atveju?

176
00:07:36,840 --> 00:07:38,500
>> Taip, taip, dvejetainis paieškos.

177
00:07:38,500 --> 00:07:42,930
Ir dvejetainis paieškos blogiausiu atveju
gali turėti elementą kažkur

178
00:07:42,930 --> 00:07:45,640
viduryje, ar kažkur
viduje masyvo.

179
00:07:45,640 --> 00:07:48,040
Bet jūs tik rasti jį, kai jūs
padalinti sąrašą per pusę, į

180
00:07:48,040 --> 00:07:48,940
pusė, per pusę, per pusę.

181
00:07:48,940 --> 00:07:50,200
Ir tada voila, tai ten.

182
00:07:50,200 --> 00:07:52,500
Arba vėl, blogiausiu atveju,
tai net ne ten.

183
00:07:52,500 --> 00:07:56,770
Bet jūs nežinote, kad jo ten nėra
kol tarsi pasiekti, kad paskutinis

184
00:07:56,770 --> 00:08:00,470
apačios dauguma elementų perpus
ir perpus ir perpus.

185
00:08:00,470 --> 00:08:01,400
>> Didelės O 1.

186
00:08:01,400 --> 00:08:03,540
Taigi, mes galime didelis O 2, didelis O 3.

187
00:08:03,540 --> 00:08:06,260
Anytime norite tik pastovų skaičių,
mes tiesiog rūšiuoti tik supaprastinti

188
00:08:06,260 --> 00:08:07,280
kad didelis O 1.

189
00:08:07,280 --> 00:08:10,440
Nors jei realiai, tai trunka
2 ar net 100 laiptelius, jei tai

190
00:08:10,440 --> 00:08:13,680
pastovus pakopų skaičius,
mes tiesiog pasakyti didelis O 1.

191
00:08:13,680 --> 00:08:15,930
Kas yra algoritmas, kuris yra
didelių O 1?

192
00:08:15,930 --> 00:08:18,350
>> PUBLIKA: Ieškoti ilgį
iš kintamąjį.

193
00:08:18,350 --> 00:08:21,090
>> Davidas Malan: Ieškoti
ilgis kintamasis?

194
00:08:21,090 --> 00:08:23,870
>> Auditorija: Ne, ilgis
jei jis jau rūšiuojamos.

195
00:08:23,870 --> 00:08:24,160
>> Davidas Malan: Geras.

196
00:08:24,160 --> 00:08:27,850
Gerai, kad rasti kažką ilgis
jei tos kažką ilgis, kaip

197
00:08:27,850 --> 00:08:30,020
masyvas, yra saugomi tam tikru kintamuoju.

198
00:08:30,020 --> 00:08:33,380
Kadangi jūs galite tik skaityti kintamąjį,
arba spausdinti kintamąjį, arba

199
00:08:33,380 --> 00:08:34,960
tiesiog paprastai gauti tą kintamąjį.

200
00:08:34,960 --> 00:08:37,299
Ir voila, kad mano pastovus laiką.

201
00:08:37,299 --> 00:08:38,909
>> Priešingai, manau, į nulio.

202
00:08:38,909 --> 00:08:42,460
Prisiminkite pirmą savaitę C
skambinti tik printf ir spausdinimas

203
00:08:42,460 --> 00:08:46,240
kažkas ekrane yra neabejotinai
pastovus laikas, nes ji tik mano

204
00:08:46,240 --> 00:08:50,880
kai procesoriaus ciklų skaičius, kurį rodo
kad ekrane tekstą.

205
00:08:50,880 --> 00:08:52,720
Arba laukti - Ar ji?

206
00:08:52,720 --> 00:08:56,430
Kaip kitaip galėtume modeliuoti
atlikimas printf?

207
00:08:56,430 --> 00:09:00,420
Ar kas nors norėtų nesutikti, kad
gal tai tikrai ne pastovus laikas?

208
00:09:00,420 --> 00:09:03,600
Kokia prasme gali printf bėga
laikas, iš tikrųjų spausdinimo juostelė

209
00:09:03,600 --> 00:09:05,580
ekranas, būti kažkas
išskyrus pastovus.

210
00:09:05,580 --> 00:09:07,860
>> Auditorija: [nesigirdi].

211
00:09:07,860 --> 00:09:08,230
>> Davidas Malan: Taip.

212
00:09:08,230 --> 00:09:09,300
Taigi tai priklauso nuo mūsų perspektyvos.

213
00:09:09,300 --> 00:09:13,390
Jei mes iš tikrųjų galvoti apie indėlio
printf kaip eilutę, ir

214
00:09:13,390 --> 00:09:16,380
Todėl mes įvertinti, kad dydis
įėjimas jo ilgis - todėl galime skambinti

215
00:09:16,380 --> 00:09:17,780
kad ilgis n, taip pat -

216
00:09:17,780 --> 00:09:21,990
be abejo, printf pati Didelės O n
nes jis ketina imtis jums n žingsnius

217
00:09:21,990 --> 00:09:24,750
spausdinti kiekvieną iš tų n
ženklai, greičiausiai.

218
00:09:24,750 --> 00:09:27,730
Bent tiek, kad mes manome,
kad gal tai naudojant už kilpos

219
00:09:27,730 --> 00:09:28,560
po gaubtu.

220
00:09:28,560 --> 00:09:30,860
>> Bet mes turime pažvelgti, kad
Kodas Norėdami suprasti geriau.

221
00:09:30,860 --> 00:09:33,650
Ir iš tiesų, kai vaikinai pradeda
analizuoti savo algoritmus, jums

222
00:09:33,650 --> 00:09:34,900
tiesiog padaryti tik tai.

223
00:09:34,900 --> 00:09:37,765
Rūšiuoti akies obuolio jūsų kodas ir manau,
apie - viskas gerai, aš turiu šį kilpa

224
00:09:37,765 --> 00:09:41,870
čia arba aš turiu įdėtos kilpos čia
tai ketinate daryti n dalykų n kartų,

225
00:09:41,870 --> 00:09:46,050
ir jūs galite rūšiuoti priežasties savo kelią
per kodą, net jei tai

226
00:09:46,050 --> 00:09:47,980
Pseudocode, o ne tikrasis kodas.

227
00:09:47,980 --> 00:09:49,730
>> Taigi, ką apie omega n kvadratu?

228
00:09:49,730 --> 00:09:53,582
Koks buvo algoritmas, kad geriausias
atveju, vis dar buvo n kvadratu žingsniai?

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

230
00:09:54,014 --> 00:09:54,880
>> Auditorija: [nesigirdi].

231
00:09:54,880 --> 00:09:55,900
>> Davidas Malan: Taigi pasirinkimas rūšiuoti.

232
00:09:55,900 --> 00:09:59,150
Kadangi šios problemos realiai sumažėtų
į tai, kad vėl, aš nežinau,

233
00:09:59,150 --> 00:10:02,600
Radau dabartinė mažiausių iki
Aš patikrinti visus prakeiktus elementai.

234
00:10:02,600 --> 00:10:08,050
Taigi, omega, tarkim, n, mes
tiesiog atėjo su vienu.

235
00:10:08,050 --> 00:10:09,300
Įtraukiama rūšiuoti.

236
00:10:09,300 --> 00:10:12,370
Jei sąrašas atsitinka būti rūšiuojami
jau, geriausiu atveju mes tiesiog

237
00:10:12,370 --> 00:10:15,090
padaryti vieną praeiti pro jį,
tuo momentu mes tikrai.

238
00:10:15,090 --> 00:10:17,890
Ir tada, kad galima teigti,
yra linijinė, tikrai.

239
00:10:17,890 --> 00:10:20,570
>> Ką apie omega 1?

240
00:10:20,570 --> 00:10:23,790
Kas, geriausiu atveju, gali trukti
pastovus pakopų skaičius?

241
00:10:23,790 --> 00:10:27,220
Taigi linijinis paieškos, jei jūs tiesiog gauti pasisekė
ir elementas jūs ieškote

242
00:10:27,220 --> 00:10:31,000
yra į dešinę nuo sąrašo pradžios,
jei tai, kur jūs pradedate savo

243
00:10:31,000 --> 00:10:33,070
linijinis Sankryþos šio sąrašo.

244
00:10:33,070 --> 00:10:35,180
>> Ir tai yra tiesa
numeris dalykų.

245
00:10:35,180 --> 00:10:37,660
Pavyzdžiui, net dvejetainis
paieška omega 1.

246
00:10:37,660 --> 00:10:40,310
Nes ką daryti, jei jums tikrai adyti
pasisekė ir pliaukštelėti-DAB viduryje

247
00:10:40,310 --> 00:10:42,950
Jūsų masyvas skaičius
jūs ieškote?

248
00:10:42,950 --> 00:10:45,730
Taigi jūs galite gauti pasisekė ten, taip pat.

249
00:10:45,730 --> 00:10:49,190
>> Tai vienas, galiausiai, omega n log n.

250
00:10:49,190 --> 00:10:52,573
Taigi n log n, mes nelabai
kalbėti apie dar, bet -

251
00:10:52,573 --> 00:10:53,300
>> Auditorija: Sujungti rūšiuoti?

252
00:10:53,300 --> 00:10:53,960
>> Davidas Malan: suliejimas rūšiuoti.

253
00:10:53,960 --> 00:10:56,920
Tai buvo paskutinį kartą Įspūdingos filmą,
kur mes pasiūlėme, o mes parodėme

254
00:10:56,920 --> 00:10:58,600
vizualiai, kad yra algoritmai.

255
00:10:58,600 --> 00:11:02,470
Ir sujungti tarsi tik vienas toks
algoritmas, kuris iš esmės yra greičiau

256
00:11:02,470 --> 00:11:03,450
nei kai kurie iš šių kitų vaikinų.

257
00:11:03,450 --> 00:11:07,800
Tiesą sakant, sujungti trumpas yra ne tik
geriausiu atveju n log n, blogiausiu

258
00:11:07,800 --> 00:11:09,460
Byla N log n.

259
00:11:09,460 --> 00:11:14,540
Ir kai jūs turite šį sutapimas
Omega ir didelis O yra tas pats?

260
00:11:14,540 --> 00:11:17,310
Mes iš tikrųjų gali apibūdinti, kad tai, kas
vadinama teta, nors tai

261
00:11:17,310 --> 00:11:18,220
šiek tiek rečiau.

262
00:11:18,220 --> 00:11:21,730
Bet tai tik reiškia, dvi ribas,
šiuo atveju yra tas pats.

263
00:11:21,730 --> 00:11:25,770
>> Taigi sujungti rūšiuoti, ką tai
tikrai skliautais mums?

264
00:11:25,770 --> 00:11:27,000
Na, prisimenu motyvaciją.

265
00:11:27,000 --> 00:11:30,340
Leiskite traukti dar vieną animaciją, kad
mes ne pažvelgti paskutinį kartą.

266
00:11:30,340 --> 00:11:33,390
Tai vienas, pati idėja, tačiau
tai šiek tiek didesnis.

267
00:11:33,390 --> 00:11:36,160
Ir aš ruošiuosi eiti į priekį ir pabrėžti
Pirmasis - mes turime įterpimo rūšiuoti

268
00:11:36,160 --> 00:11:39,410
viršuje, kairėje, tada pasirinkimas rūšiuoti,
burbulas rūšiuoti, kitų rūšių pora -

269
00:11:39,410 --> 00:11:42,670
korpuso ir greitai - kad mes ne kalbėjo
apie, ir krūva ir sujungti rūšiuoti.

270
00:11:42,670 --> 00:11:47,090
>> Taigi, bent pabandyti sutelkti savo akis
trijų geriausių į kairę, tada į

271
00:11:47,090 --> 00:11:49,120
sujungti rūšiuoti, kai aš spustelėkite
tai žalia rodyklė.

272
00:11:49,120 --> 00:11:51,900
Bet aš tegul juos visus paleisti, tiesiog
jums įvairovę jausmą,

273
00:11:51,900 --> 00:11:53,980
algoritmai, kurie egzistuoja pasaulyje.

274
00:11:53,980 --> 00:11:56,180
Aš ruošiuosi leisti Šios įsibėgėjimo
vos kelias sekundes.

275
00:11:56,180 --> 00:11:59,640
Ir jei jums sutelkti savo akis - pasirinkti
algoritmas, sutelkti dėmesį į jį tik

276
00:11:59,640 --> 00:12:02,970
s - jums pradėti rodyti
modelis, kad tai įgyvendinti.

277
00:12:02,970 --> 00:12:04,530
>> Sujungti rūšiuoti, pranešime, yra padaryta.

278
00:12:04,530 --> 00:12:06,430
Heap rūšiuoti, greitai rūšiuoti, kriauklių -

279
00:12:06,430 --> 00:12:09,480
todėl atrodo, kad mes pristatė tris
blogiausia algoritmai praėjusią savaitę.

280
00:12:09,480 --> 00:12:12,960
Bet tai gerai, kad mes čia šiandien
pažvelgti suliejimo rūšiuoti, kuris yra vienas iš

281
00:12:12,960 --> 00:12:16,500
tuo lengviau tie yra pažvelgti, net
nors ji tikriausiai bus lenkimo jūsų protas

282
00:12:16,500 --> 00:12:17,490
tik truputį.

283
00:12:17,490 --> 00:12:21,130
Čia mes matome, kiek daug
pasirinkimas rūšiuoti sucks.

284
00:12:21,130 --> 00:12:24,600
>> Tačiau atvirkštinė pusė, tai
tikrai lengva įgyvendinti.

285
00:12:24,600 --> 00:12:28,160
Ir gal P Set 3, tai viena iš
algoritmai Jūs pasirinkote įgyvendinti

286
00:12:28,160 --> 00:12:28,960
už standartinę versiją.

287
00:12:28,960 --> 00:12:30,970
Puikiai gerai, puikiai teisinga.

288
00:12:30,970 --> 00:12:35,210
>> Bet vėl, kaip n tampa didelis, jei
nuspręsti įgyvendinti greičiau algoritmą

289
00:12:35,210 --> 00:12:39,020
kaip sujungti rūšiuoti, šansai yra didesni ir
Didesnės sąnaudos, jūsų kodas yra tik

290
00:12:39,020 --> 00:12:39,800
ketina paleisti greičiau.

291
00:12:39,800 --> 00:12:41,090
Jūsų svetainė ketina dirbti geriau.

292
00:12:41,090 --> 00:12:42,650
Jūsų vartotojai bus laimingesni.

293
00:12:42,650 --> 00:12:45,280
Ir taip yra šie poveikiai
faktiškai suteikiant

294
00:12:45,280 --> 00:12:47,350
mums kai giliau minties.

295
00:12:47,350 --> 00:12:49,990
>> Taigi galime pažvelgti, kas sujungti išvaizdą
rūšiuoti yra iš tikrųjų visi apie.

296
00:12:49,990 --> 00:12:52,992
The cool dalykas yra tai, kad sujungti
rūšiuoti yra tik tai.

297
00:12:52,992 --> 00:12:56,300
Tai, vėlgi, ką mes vadinami
Pseudocode, Pseudocode būtybė

298
00:12:56,300 --> 00:12:57,720
Lietuvių-kaip sintaksė.

299
00:12:57,720 --> 00:12:59,890
Ir paprastumas yra
rūšiuoti įspūdingi.

300
00:12:59,890 --> 00:13:02,840
>> Taigi ant įvesties n elementų - taip, kad
tiesiog reiškia, štai masyvas.

301
00:13:02,840 --> 00:13:04,000
Jis gavo n dalykų į jį.

302
00:13:04,000 --> 00:13:05,370
Tai viskas, ką sakote ten.

303
00:13:05,370 --> 00:13:07,560
>> Jei n yra mažesnis nei 2, grįžti.

304
00:13:07,560 --> 00:13:08,640
Taigi, tai tik nereikšmingas atvejis.

305
00:13:08,640 --> 00:13:12,580
Jei n yra mažesnis nei 2, tada, žinoma, ji yra
1 arba 0, tokiu atveju dalykas

306
00:13:12,580 --> 00:13:14,780
jau surūšiuotus arba neegzistuoja,
tad tiesiog grįžti.

307
00:13:14,780 --> 00:13:15,900
Nėra nieko daryti.

308
00:13:15,900 --> 00:13:18,360
Štai paprastas bylą roviau.

309
00:13:18,360 --> 00:13:20,110
>> Kitur, mes turime tris veiksmus.

310
00:13:20,110 --> 00:13:23,650
Rūšiuoti kairėje pusėje, elementų, rūšiavimo
Dešinė pusė iš elementų,

311
00:13:23,650 --> 00:13:26,650
ir tada sujungti surūšiuoti puses.

312
00:13:26,650 --> 00:13:29,400
Kas įdomu, kad čia yra
Aš tipo punting, tiesa?

313
00:13:29,400 --> 00:13:32,300
Yra rūšies apskrito apibrėžimo
šį algoritmą.

314
00:13:32,300 --> 00:13:35,986
Kokia prasme tai algoritmo
raiškos apskritas?

315
00:13:35,986 --> 00:13:37,850
>> Auditorija: [nesigirdi].

316
00:13:37,850 --> 00:13:41,670
>> Davidas Malan: Taip, mano rūšiavimo algoritmas,
du jos žingsniai yra "rūšiuoti

317
00:13:41,670 --> 00:13:44,640
kažkas. "Ir taip, kad kyla
klausimas, gerai, ką aš ketinate naudoti

318
00:13:44,640 --> 00:13:46,460
rūšiuoti kairę pusę
ir į dešinę pusę?

319
00:13:46,460 --> 00:13:49,600
Ir grožis čia yra tai, kad nors
Vėlgi, tai yra proto-lenkimo

320
00:13:49,600 --> 00:13:54,030
dalis potencialiai, galite naudoti tą patį
algoritmas rūšiuoti kairę pusę.

321
00:13:54,030 --> 00:13:54,700
>> Bet palauk.

322
00:13:54,700 --> 00:13:57,070
Kai jūs pasakojo rūšiuoti
kairė pusė, kas yra du

323
00:13:57,070 --> 00:13:58,240
veiksmai bus toliau?

324
00:13:58,240 --> 00:14:00,550
Mes rūšiuoti kairę pusę
kairėje pusėje, ir dešinėje

325
00:14:00,550 --> 00:14:01,420
pusė kairėje pusėje.

326
00:14:01,420 --> 00:14:04,430
Velnias, kaip man sutvarkyti tuos du
pusės arba ketvirčiai, o dabar?

327
00:14:04,430 --> 00:14:05,260
>> Bet tai gerai.

328
00:14:05,260 --> 00:14:07,830
Mes turime rūšiavimo algoritmą čia.

329
00:14:07,830 --> 00:14:10,660
Ir nors jums gali nerimauti ne
pirmas tai rūšies begalinis

330
00:14:10,660 --> 00:14:12,780
kilpa, tai ciklas, kad niekada
ketina baigti - ji ketina

331
00:14:12,780 --> 00:14:15,770
baigsis tada, kai kas atsitiks?

332
00:14:15,770 --> 00:14:16,970
Kai n yra mažiau nei 2.

333
00:14:16,970 --> 00:14:19,180
Kuris galiausiai nutiks,
nes jei jūs nuolat perpus sumažinti ir

334
00:14:19,180 --> 00:14:23,020
perpus sumažinti per pusę sumažinti šias puses, be abejo,
galų gale jūs ketinate baigti

335
00:14:23,020 --> 00:14:25,350
iki vos 1 arba 0 elementus.

336
00:14:25,350 --> 00:14:28,500
Kuriuo šis algoritmas
sako viskas.

337
00:14:28,500 --> 00:14:31,020
>> Taigi reali magija tai
algoritmas atrodo,

338
00:14:31,020 --> 00:14:33,470
kad galutinis žingsnis, sujungimo.

339
00:14:33,470 --> 00:14:37,190
Tai paprasta idėja tiesiog sujungti du
dalykų, tai, kas galiausiai bus

340
00:14:37,190 --> 00:14:40,920
leisti mums rūšiuoti masyvas,
tarkim, aštuonis elementus.

341
00:14:40,920 --> 00:14:44,410
Taigi turiu aštuonis daugiau streso kamuoliukus iki
čia aštuonių popieriaus lapų, ir vienas

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

343
00:14:45,500 --> 00:14:46,140
kuris man išsaugoti.

344
00:14:46,140 --> 00:14:46,960
>> [Juokas]

345
00:14:46,960 --> 00:14:48,970
>> Davidas Malan: Jei mes galime imtis aštuonių
savanoriai, ir pažiūrėkime, jei mes galime

346
00:14:48,970 --> 00:14:51,430
žaisti šį, ir todėl.

347
00:14:51,430 --> 00:14:52,500
Oho, Gerai.

348
00:14:52,500 --> 00:14:53,565
Kompiuterių mokslas vis įdomus.

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

350
00:14:54,320 --> 00:14:57,770
Taigi, kaip apie jus tris,
Didžiausias ranka ten.

351
00:14:57,770 --> 00:14:58,580
Keturi iš nugaros.

352
00:14:58,580 --> 00:15:02,220
Ir kaip apie mes padarysime jus
trys šios eilutės?

353
00:15:02,220 --> 00:15:03,390
Ant priekinės keturis.

354
00:15:03,390 --> 00:15:04,920
Taigi jūs aštuoneri, ateiti iki.

355
00:15:04,920 --> 00:15:12,060
>> [Juokas]

356
00:15:12,060 --> 00:15:13,450
>> Davidas Malan: Aš iš tikrųjų
nežinote, kas tai yra.

357
00:15:13,450 --> 00:15:14,810
Ar tai stresas kamuoliukai?

358
00:15:14,810 --> 00:15:16,510
Stalo lempos?

359
00:15:16,510 --> 00:15:18,650
Medžiaga?

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

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

362
00:15:20,160 --> 00:15:21,310
Taigi atėjo iki.

363
00:15:21,310 --> 00:15:22,310
Kas norėtų -

364
00:15:22,310 --> 00:15:23,570
nuolat artėja.

365
00:15:23,570 --> 00:15:24,240
Pažiūrėkime.

366
00:15:24,240 --> 00:15:26,460
Ir tai kelia jums vietoje -

367
00:15:26,460 --> 00:15:27,940
esate vietoje vienos.

368
00:15:27,940 --> 00:15:28,670
Uh-Oh, wait a minute.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - O, gerai.

370
00:15:30,760 --> 00:15:31,310
Gerai, mes geri.

371
00:15:31,310 --> 00:15:35,130
Gerai, kad kiekvienas turi savo vietą,
bet ne "Google" stiklo.

372
00:15:35,130 --> 00:15:36,475
Leiskite man į eilę Šie padidintos.

373
00:15:36,475 --> 00:15:37,115
Koks tavo vardas?

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

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

376
00:15:38,090 --> 00:15:42,000
Gerai, jums atrodys
Geek, jei tai Gerai.

377
00:15:42,000 --> 00:15:44,625
Na, aš taip pat manau,
tik akimirką.

378
00:15:44,625 --> 00:15:45,875
Viskas gerai, laukimo.

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

380
00:15:48,510 --> 00:15:50,950
Mes jau bando sugalvoti
naudojimo atveju "Google Stiklas ir mes

381
00:15:50,950 --> 00:15:53,750
maniau, kad būtų smagu tiesiog
tai, kai žmonės ant scenos.

382
00:15:53,750 --> 00:15:57,120
Mes įrašysime pasaulį
iš savo perspektyvos.

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

384
00:15:58,410 --> 00:15:59,830
Ne tikriausiai, ką "Google paskirtį.

385
00:15:59,830 --> 00:16:02,260
Gerai, jei jūs neprieštaraujate dėvėti
ir ateinančius nepatogios minučių,

386
00:16:02,260 --> 00:16:03,150
kad būtų nuostabu.

387
00:16:03,150 --> 00:16:08,620
>> Gerai, kad mes turime čia masyvas
elementai, ir kad masyvo, pagal

388
00:16:08,620 --> 00:16:11,480
popieriaus gabaliukų šių žmonių "
rankas, šiuo metu nerūšiuotos.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: O, kad taip keistai.

390
00:16:12,050 --> 00:16:12,810
>> Davidas Malan: Tai gana daug atsitiktinai.

391
00:16:12,810 --> 00:16:15,760
Ir tik akimirką, mes ketiname bandyti
įgyvendinti sujungti rūšiuoti kartu

392
00:16:15,760 --> 00:16:17,950
ir pamatyti, kur tas raktas įžvalga.

393
00:16:17,950 --> 00:16:21,970
Ir triukas čia suliejimo rūšiuoti yra
kažkas, kad mes ne prielaida dar.

394
00:16:21,970 --> 00:16:24,030
Mes iš tikrųjų reikia šiek tiek
papildomos vietos.

395
00:16:24,030 --> 00:16:26,650
Taigi, kas bus ypač
įdomu tai, kad šie

396
00:16:26,650 --> 00:16:29,270
vaikinai ketinate judėti mažai
tiek, nes aš ruošiuosi daryti prielaidą, kad

397
00:16:29,270 --> 00:16:31,880
ten papildomai masyvas erdvėje,
pasakyti, tiesiai už jų.

398
00:16:31,880 --> 00:16:34,570
>> Taigi, jei jie už savo kėdę,
tai antrinė masyvo.

399
00:16:34,570 --> 00:16:36,960
Jei jie sėdi čia, tai
pagrindinis masyvo.

400
00:16:36,960 --> 00:16:40,170
Bet tai išteklių, kad mes turime
nenaudoja finansinio sverto iki šiol su burbulas

401
00:16:40,170 --> 00:16:42,040
rūšiuoti, su atrankos rūšiuoti,
su prierašu rūšiuoti.

402
00:16:42,040 --> 00:16:44,600
Prisiminkite, praeitą savaitę, visi tik
rūšies išmaišytos vietoje.

403
00:16:44,600 --> 00:16:46,840
Jie nebuvo naudoti bet kokią papildomą atmintį.

404
00:16:46,840 --> 00:16:49,310
Mes padarėme vietos žmones
judančių žmonių aplink.

405
00:16:49,310 --> 00:16:50,580
>> Taigi tai yra pagrindinis įžvalgos, taip pat.

406
00:16:50,580 --> 00:16:53,410
Yra tai kompromisas, apskritai į
kompiuterių mokslas, išteklius.

407
00:16:53,410 --> 00:16:55,800
Jei norite pagreitinti kažką
kaip laiko, jūs ketinate

408
00:16:55,800 --> 00:16:56,900
turi mokėti kainą.

409
00:16:56,900 --> 00:17:00,750
Ir vienas iš šių kainų yra labai dažnai
erdvė, atminties kiekis ar sunku

410
00:17:00,750 --> 00:17:01,700
diske, kad jūs naudojate.

411
00:17:01,700 --> 00:17:03,640
Arba, tiesą sakant, suma
programuotojas metu.

412
00:17:03,640 --> 00:17:06,700
Kiek laiko užtrunka jums, žmogaus,
realiai įgyvendinti šiek tiek daugiau

413
00:17:06,700 --> 00:17:07,829
sudėtingas algoritmas.

414
00:17:07,829 --> 00:17:09,760
Bet šiandien, kompromisas
yra laikas ir erdvė.

415
00:17:09,760 --> 00:17:11,930
>> Taigi, jei jus vaikinai gali tiesiog telpa jūsų
numerius, mes galime pamatyti, kad esate

416
00:17:11,930 --> 00:17:15,839
iš tiesų suderinti 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Puikus.

418
00:17:16,599 --> 00:17:19,520
Taigi, aš ruošiuosi pabandyti muzikinės
dalykų, jei jus vaikinai gali tik

419
00:17:19,520 --> 00:17:21,800
sekti mano pavyzdžiu čia.

420
00:17:21,800 --> 00:17:26,650
>> Taigi, aš ketina įgyvendinti, visų pirma,
Pirmasis žingsnis pseudocode, kuris yra

421
00:17:26,650 --> 00:17:29,440
į įvesties n elementų, jei n
mažiau nei 2, tada grįžti.

422
00:17:29,440 --> 00:17:31,370
Akivaizdu, kad nėra
taikoma, todėl mes judėti pirmyn.

423
00:17:31,370 --> 00:17:33,340
Taigi rūšiuoti kairėje pusėje, elementai.

424
00:17:33,340 --> 00:17:36,220
Taigi, tai reiškia aš norėčiau sutelkti dėmesį mano
dėmesys tik į tai metu

425
00:17:36,220 --> 00:17:37,310
Keturi vaikinai čia.

426
00:17:37,310 --> 00:17:39,774
Viskas gerai, ką aš kitą daryti?

427
00:17:39,774 --> 00:17:40,570
>> Auditorija: Rūšiuoti kairę pusę.

428
00:17:40,570 --> 00:17:42,780
>> Davidas Malan: Taigi, dabar turiu sutvarkyti
kairė pusė šių vaikinai.

429
00:17:42,780 --> 00:17:45,580
Nes vėl prisiimti sau į
tikslas rūšiuoti kairę pusę.

430
00:17:45,580 --> 00:17:46,440
Kaip tai padaryti?

431
00:17:46,440 --> 00:17:49,140
Tiesiog sekite instrukcijas, net
nors mes darome jį dar kartą.

432
00:17:49,140 --> 00:17:50,160
Taigi rūšiuoti kairę pusę.

433
00:17:50,160 --> 00:17:52,030
Dabar aš rūšiavimo šiuos du vaikinai.

434
00:17:52,030 --> 00:17:53,563
Kas toliau?

435
00:17:53,563 --> 00:17:54,510
>> Auditorija: Rūšiuoti kairę pusę.

436
00:17:54,510 --> 00:17:55,460
>> Davidas Malan: Rūšiuoti kairę pusę.

437
00:17:55,460 --> 00:18:00,680
Taigi, dabar jų, ši vieta čia
yra 1 dydžio sąrašą.

438
00:18:00,680 --> 00:18:01,365
Ir kas tavo vardas?

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

440
00:18:02,390 --> 00:18:03,690
>> Davidas Malan: princesė Daisy yra čia.

441
00:18:03,690 --> 00:18:07,470
Ir taip ji jau rūšiuojamos, nes
sąrašas dydžio 1.

442
00:18:07,470 --> 00:18:09,490
Ką man kitą daryti?

443
00:18:09,490 --> 00:18:13,680
Gerai, negrąžinti, nes šis sąrašas yra
1 dydis, kuris yra mažiau nei 2.

444
00:18:13,680 --> 00:18:14,320
Tada kas sekantis žingsnis?

445
00:18:14,320 --> 00:18:17,490
Ir dabar jūs turite rūšies
Atsitraukia savo mintis.

446
00:18:17,490 --> 00:18:19,340
>> Rūšiuoti teisingą pusę, kuri yra -

447
00:18:19,340 --> 00:18:19,570
koks tavo vardas?

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

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

450
00:18:20,980 --> 00:18:23,210
Ir taip, tai ką mes darome dabar,
turime 1 dydžio sąrašą?

451
00:18:23,210 --> 00:18:24,440
>> Auditorija: Atgal.

452
00:18:24,440 --> 00:18:24,760
>> Davidas Malan: Atsargiai.

453
00:18:24,760 --> 00:18:29,540
Mes vėl pirmas, o dabar trečioji
žingsnis - ir jei aš tipo vaizduoti jį

454
00:18:29,540 --> 00:18:33,490
apimantis dvi vietas dabar, dabar aš
turi sujungti šiuos du elementus.

455
00:18:33,490 --> 00:18:35,530
Taigi, dabar, deja, elementai
yra ne iš eilės.

456
00:18:35,530 --> 00:18:39,920
Bet tai kur sujungimo procesas
pradeda gauti įtikinamos.

457
00:18:39,920 --> 00:18:42,410
>> Taigi, jei jus vaikinai gali atsistoti tik
momentas, aš ruošiuosi reikia tavęs, kad

458
00:18:42,410 --> 00:18:44,170
momentas, stiprindamas už savo kėdės.

459
00:18:44,170 --> 00:18:46,480
O jei Linda, nes 2 yra
mažesnis nei 4, kodėl gi ne

460
00:18:46,480 --> 00:18:48,130
Jūs ateiti aplink pirmas?

461
00:18:48,130 --> 00:18:48,690
Ten pasilikti.

462
00:18:48,690 --> 00:18:50,520
Taigi Linda, jūs ateiti aplink pirmas.

463
00:18:50,520 --> 00:18:53,820
>> Dabar iš tikrųjų jei tai tik matrica
mes galime tiesiog perkelti ją realiu laiku

464
00:18:53,820 --> 00:18:55,360
iš šios kėdės šioje vietoje.

465
00:18:55,360 --> 00:18:57,770
Taigi, įsivaizduokite, kad paėmė pastovus
pakopų skaičius 1.

466
00:18:57,770 --> 00:18:58,480
O dabar -

467
00:18:58,480 --> 00:19:01,490
bet mes turime padėti jums
pirmoji vieta čia.

468
00:19:01,490 --> 00:19:03,930
>> Ir dabar, jei gali ateiti aplink,
kaip gerai, kad mes ketiname

469
00:19:03,930 --> 00:19:06,300
būti vietoje dviejų.

470
00:19:06,300 --> 00:19:09,120
Ir nors tai jaučiasi tai
atsižvelgiant į laiką, kas malonu dabar

471
00:19:09,120 --> 00:19:14,710
kad kairė pusė
kairėje pusėje, dabar rūšiuojamos.

472
00:19:14,710 --> 00:19:18,010
Taigi, kas buvo kitas žingsnis, jei mes dabar
atgal toliau į istoriją?

473
00:19:18,010 --> 00:19:18,980
>> Auditorija: Dešinė pusė.

474
00:19:18,980 --> 00:19:19,900
>> Davidas Malan: Rūšiuoti tinkamą pusę.

475
00:19:19,900 --> 00:19:21,320
Taigi jus vaikinai tai padaryti, taip pat.

476
00:19:21,320 --> 00:19:23,510
Taigi, jei galite atsistoti
tik akimirką?

477
00:19:23,510 --> 00:19:25,192
Ir kas yra jūsų vardas?

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

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

480
00:19:25,870 --> 00:19:29,720
Gerai, kad Jess dabar į kairę
pusę dešinėje pusėje.

481
00:19:29,720 --> 00:19:31,400
Ir taip ji dydžio 1 sąrašas.

482
00:19:31,400 --> 00:19:32,380
Ji akivaizdžiai surūšiuoti.

483
00:19:32,380 --> 00:19:33,070
Ir tavo vardas?

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

485
00:19:33,630 --> 00:19:35,340
>> Davidas Malan: Michelle akivaizdžiai
dydžio 1 sąrašas.

486
00:19:35,340 --> 00:19:36,050
Ji jau sutvarkyti.

487
00:19:36,050 --> 00:19:38,690
Taigi dabar magija atsitiks,
jungimosi procesą.

488
00:19:38,690 --> 00:19:39,790
Taigi, kas vyksta atėjai, pirmas?

489
00:19:39,790 --> 00:19:41,560
Akivaizdu Michelle.

490
00:19:41,560 --> 00:19:43,280
Taigi, jei galite ateiti aplink atgal.

491
00:19:43,280 --> 00:19:47,090
Erdvė mes turime rasti jai dabar
Iškart už šios kėdę.

492
00:19:47,090 --> 00:19:51,580
Ir dabar, jei galėtumėte grįžti, taip pat,
dabar mes turime, turi būti aišku, du

493
00:19:51,580 --> 00:19:53,810
pusės, kiekvienas dydis 2 -

494
00:19:53,810 --> 00:19:57,090
ir tik vaizdavimas meilės, jei
galėtų šiek tiek erdvėje -

495
00:19:57,090 --> 00:19:59,780
vienas kairėje pusė čia vienas
Dešinė pusė čia.

496
00:19:59,780 --> 00:20:01,160
>> Atsukti toliau istorija.

497
00:20:01,160 --> 00:20:02,270
Kas žingsnis yra šalia?

498
00:20:02,270 --> 00:20:03,030
>> Auditorija: Sujungti.

499
00:20:03,030 --> 00:20:04,160
>> Davidas Malan: Taigi dabar mes turime sujungti.

500
00:20:04,160 --> 00:20:07,490
Taigi Gerai, kad dabar, laimei, mes
tiesiog atlaisvinti keturis kėdės.

501
00:20:07,490 --> 00:20:11,480
Taigi mes naudojame dvigubai daugiau atminties, bet
mes galime suteikti flip-flop'e tarp

502
00:20:11,480 --> 00:20:12,330
dvi matricas.

503
00:20:12,330 --> 00:20:14,190
Taigi, kuris skaičius yra atėjai, pirmas?

504
00:20:14,190 --> 00:20:14,850
Taigi Michelle, žinoma.

505
00:20:14,850 --> 00:20:16,680
Taigi ateiti aplink ir imtis
Jūsų vieta čia.

506
00:20:16,680 --> 00:20:19,120
Ir tada numeris 2 yra akivaizdžiai
kitą, todėl jūs ateiti čia.

507
00:20:19,120 --> 00:20:21,520
Numeris 4 numeris 6.

508
00:20:21,520 --> 00:20:23,390
Ir vėl, nors ten
Šiek tiek pėsčiųjų dalyvauja,

509
00:20:23,390 --> 00:20:26,010
tikrai, tai gali įvykti akimirksniu,
perkeldami vieną -

510
00:20:26,010 --> 00:20:26,880
Gerai, gerai grojo.

511
00:20:26,880 --> 00:20:28,350
>> [Juokas]

512
00:20:28,350 --> 00:20:29,680
>> Davidas Malan: O dabar mes
gana geros formos.

513
00:20:29,680 --> 00:20:34,910
Kairėje pusėje, visą
įvesties jau rūšiuojamos.

514
00:20:34,910 --> 00:20:37,370
Gerai, kad šie vaikinai buvo
iš mano privalumas -

515
00:20:37,370 --> 00:20:40,340
kaip ji galų gale visus ant merginos
į kairę ir visi ant dešinės berniukai?

516
00:20:40,340 --> 00:20:42,450
>> Gerai, kad vaikinai "eilė dabar.

517
00:20:42,450 --> 00:20:44,680
Taigi aš ne vaikščioti jus per
šiuos veiksmus.

518
00:20:44,680 --> 00:20:46,550
Mes pamatyti, jei mes galime iš naujo
pats Pseudocode.

519
00:20:46,550 --> 00:20:50,050
Jei norite eiti į priekį ir atsistoti,
ir vaikinai, leiskite man duoti jums mikrofono.

520
00:20:50,050 --> 00:20:52,990
Žr jeigu jūs galite ne atkartoti tai, ką
mes tiesiog padarė čia

521
00:20:52,990 --> 00:20:53,880
kitas galas sąrašo.

522
00:20:53,880 --> 00:20:59,530
Kas turi kalbėti pirma,
remiantis algoritmas?

523
00:20:59,530 --> 00:21:03,210
Taigi, paaiškinti, ką darai prieš
jums jokių pėdų judesius.

524
00:21:03,210 --> 00:21:05,930
>> GARSIAKALBIS 1: Gerai, kad jau
Esu kairę pusę

525
00:21:05,930 --> 00:21:07,790
kairėje pusėje, vėl grįšiu.

526
00:21:07,790 --> 00:21:08,730
Teisė?

527
00:21:08,730 --> 00:21:09,250
>> Davidas Malan: Geras.

528
00:21:09,250 --> 00:21:10,350
>> GARSIAKALBIS 1: Ir tada -

529
00:21:10,350 --> 00:21:11,800
>> Davidas Malan: Kas daro
mic eiti toliau?

530
00:21:11,800 --> 00:21:12,920
>> GARSIAKALBIS 1 Kitas skaičius.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Taigi, aš į dešinę pusę
iš kairėje pusėje

532
00:21:14,720 --> 00:21:17,830
kairė pusė, ir aš grįžti.

533
00:21:17,830 --> 00:21:18,050
>> Davidas Malan: Geras.

534
00:21:18,050 --> 00:21:18,550
Grįšite.

535
00:21:18,550 --> 00:21:21,855
Taigi dabar kas kitas už jus du?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Mes norime pamatyti, kas yra mažesnis.

537
00:21:23,740 --> 00:21:24,200
>> Davidas Malan: Būtent.

538
00:21:24,200 --> 00:21:24,940
Mes norime sujungti.

539
00:21:24,940 --> 00:21:27,590
Erdvė mes ketiname naudoti sujungti
jūs į, nors jie

540
00:21:27,590 --> 00:21:30,250
Akivaizdu, surūšiuoti jau mes ketiname
laikytis tos pačios algoritmą.

541
00:21:30,250 --> 00:21:31,560
Taigi, kas eina atgal pirmiausia?

542
00:21:31,560 --> 00:21:35,720
Taigi 3, tada 7.

543
00:21:35,720 --> 00:21:38,570
Ir dabar mikrofono eina
šių vaikinai, gerai?

544
00:21:38,570 --> 00:21:43,590
>> GARSIAKALBIS 3: Taigi, aš į dešinę pusę
į kairę pusę, o mano n yra mažesnis nei

545
00:21:43,590 --> 00:21:45,048
1, todėl aš tik ketina perduoti -

546
00:21:45,048 --> 00:21:46,380
>> Davidas Malan: Geras.

547
00:21:46,380 --> 00:21:49,450
>> GARSIAKALBIS 4 Aš teisė pusė
Dešinė pusė iš dešinės pusės, ir aš

548
00:21:49,450 --> 00:21:51,740
taip pat vienas asmuo, todėl aš
ketina grįžti.

549
00:21:51,740 --> 00:21:52,990
Taigi dabar mes sulieti.

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

551
00:21:55,140 --> 00:21:56,150
>> GARSIAKALBIS 3: Taigi mes einame atgal.

552
00:21:56,150 --> 00:21:57,160
>> Davidas Malan: Taigi jūs einate į nugarą.

553
00:21:57,160 --> 00:21:59,200
Taigi 5 eina, tada 8.

554
00:21:59,200 --> 00:22:01,240
Ir dabar auditorijos, kuri yra
žingsnis turime dabar atsukti

555
00:22:01,240 --> 00:22:02,200
atgal į mūsų protus?

556
00:22:02,200 --> 00:22:02,940
>> Auditorija: Sujungti.

557
00:22:02,940 --> 00:22:07,270
>> Davidas Malan: sujungimas kairėje pusėje, ir dešinėje
pusė pradinio kairę pusę.

558
00:22:07,270 --> 00:22:08,840
Taigi dabar -

559
00:22:08,840 --> 00:22:10,520
ir tiesiog padaryti tai aišku,
padaryti šiek tiek vietos

560
00:22:10,520 --> 00:22:11,690
tarp jūsų du vaikinai.

561
00:22:11,690 --> 00:22:13,800
Taigi dabar, kad yra du sąrašai,
kairę ir dešinę.

562
00:22:13,800 --> 00:22:18,320
Taigi, kaip mes dabar sujungti jus vaikinai į
priekinė sėdynių eilė naujo?

563
00:22:18,320 --> 00:22:19,600
>> 3 eina pirma.

564
00:22:19,600 --> 00:22:20,850
Tada 5, žinoma.

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

566
00:22:23,110 --> 00:22:27,330
Tada 7, o dabar 8.

567
00:22:27,330 --> 00:22:28,710
Gerai, dabar mes esame?

568
00:22:28,710 --> 00:22:29,650
>> Auditorija: Neatlikta.

569
00:22:29,650 --> 00:22:32,440
>> Davidas Malan: Ne padaryti, nes
be abejo, yra vienas žingsnis liko.

570
00:22:32,440 --> 00:22:35,720
Bet vėl, todėl aš naudoju tai
žargonas kaip "atsukti savo mintis",

571
00:22:35,720 --> 00:22:37,160
tai todėl, kad tikrai
kas vyksta.

572
00:22:37,160 --> 00:22:39,610
Mes ketiname per visus šiuos veiksmus,
bet mes tarsi pristabdę

573
00:22:39,610 --> 00:22:42,480
momentas, nardymas giliau į
algoritmas, pristabdę for a moment,

574
00:22:42,480 --> 00:22:45,840
nardymas giliau į algoritmą ir
dabar mes turime rūšiuoti atsukti mūsų

575
00:22:45,840 --> 00:22:49,430
protus ir atšaukti visų šių sluoksnių
kad mes tarsi užlaikomas.

576
00:22:49,430 --> 00:22:51,790
>> Taigi dabar mes turime du sąrašus dydžio 4.

577
00:22:51,790 --> 00:22:54,790
Jei vaikinai galėtų atsistoti paskutinį kartą
ir padaryti daug diske čia

578
00:22:54,790 --> 00:22:57,230
aiškiai nurodyti, kad tai yra kairėje
pusė originalus,

579
00:22:57,230 --> 00:22:58,620
Dešinė pusė iš originalo.

580
00:22:58,620 --> 00:23:01,060
Kas pirmas skaičius, kad mes
reikia traukti į nugarą?

581
00:23:01,060 --> 00:23:01,870
Michelle, žinoma.

582
00:23:01,870 --> 00:23:03,230
>> Taigi, mes įdėti Michelle čia.

583
00:23:03,230 --> 00:23:05,080
Ir kas yra skaičius 2?

584
00:23:05,080 --> 00:23:06,440
Numeris 2 ateina atgal taip pat.

585
00:23:06,440 --> 00:23:07,800
Numeris 3?

586
00:23:07,800 --> 00:23:08,510
Puikus.

587
00:23:08,510 --> 00:23:16,570
Numeris 4 numeris 5 numeris 6
numeris 7 ir skaičius 8.

588
00:23:16,570 --> 00:23:18,850
>> Gerai, kad ji jautėsi kaip daug
žingsnių, tikrai.

589
00:23:18,850 --> 00:23:22,390
Bet dabar pažiūrėkime, jei mes negalime patvirtinti
tarsi intuityviai, kad šis

590
00:23:22,390 --> 00:23:26,190
algoritmas iš esmės, ypač
n bus tikrai didelis, kaip matėme

591
00:23:26,190 --> 00:23:29,170
su animacija, yra
iš esmės greičiau.

592
00:23:29,170 --> 00:23:33,400
Taigi galiu reikalauti šį algoritmą, kad blogiausia
atveju ir net geriausiu atveju,

593
00:23:33,400 --> 00:23:36,160
yra didelis O n kartų log n.

594
00:23:36,160 --> 00:23:39,160
Tai yra, ten kai šis aspektas
algoritmas, kuris trunka n žingsnių, tačiau

595
00:23:39,160 --> 00:23:43,110
yra ir kitas aspektas kažkur
kad iteracija, kad apsisukimo, kad

596
00:23:43,110 --> 00:23:44,410
trunka log n žingsnių.

597
00:23:44,410 --> 00:23:49,154
Mes galime įdėti mūsų pirštu, ką tie
du skaičiai omenyje?

598
00:23:49,154 --> 00:23:51,320
Na, kur -

599
00:23:51,320 --> 00:23:54,160
where'd mikrofono eiti?

600
00:23:54,160 --> 00:23:58,660
>> GARSIAKALBIS 1: Ar prisijungti, kad n
nesilaikantiems mus į dvi -

601
00:23:58,660 --> 00:23:59,630
padalijus iš dviejų, iš esmės.

602
00:23:59,630 --> 00:24:00,120
>> Davidas Malan: Būtent.

603
00:24:00,120 --> 00:24:03,000
Bet kuriuo metu mes matome, bet algoritmas taigi
kas ten buvo tai modelis

604
00:24:03,000 --> 00:24:04,200
dalijimas, dalijimas, dalijant.

605
00:24:04,200 --> 00:24:05,700
Ir tai paprastai sumažinama
į kažką, kad

606
00:24:05,700 --> 00:24:07,100
logaritminė, prisijunkite bazė 2.

607
00:24:07,100 --> 00:24:10,180
Bet tai tikrai galėjo būti bet kas,
bet prisijungti bazę 2.

608
00:24:10,180 --> 00:24:11,330
>> Dabar ką apie n?

609
00:24:11,330 --> 00:24:14,550
Matau, kad mes tipo suskirstyti jus
vaikinai - suskirstyti jus, padalintas jums,

610
00:24:14,550 --> 00:24:15,910
suskirstyti jus, padalintas jums.

611
00:24:15,910 --> 00:24:18,760
Kur atėjo galas iš?

612
00:24:18,760 --> 00:24:19,810
>> Taigi tai sujungti.

613
00:24:19,810 --> 00:24:20,610
Kadangi apie tai galvoti.

614
00:24:20,610 --> 00:24:25,420
Jei sujungti aštuonis žmones,
kai pusė iš jų yra keturių rinkinys

615
00:24:25,420 --> 00:24:27,770
ir kita pusė yra vienas
nustatyti iš keturių, kaip tu

616
00:24:27,770 --> 00:24:28,820
apie tai sujungti?

617
00:24:28,820 --> 00:24:30,830
Na, vaikinai padarė
gana intuityviai.

618
00:24:30,830 --> 00:24:34,140
>> Bet jei aš, o ne tai padarė šiek tiek daugiau
metodiškai, aš galėjo nurodė

619
00:24:34,140 --> 00:24:38,090
kairiausias asmuo pirmą kartą su mano kairę
Kita vertus, nurodė kairiausias asmeniui

620
00:24:38,090 --> 00:24:42,080
tos su mano dešinėje pusėje, ir
tik vėliau perėjau

621
00:24:42,080 --> 00:24:46,990
sąrašas, nurodant bent mažiausio elemento
kiekvieną kartą, juda mano pirštu per ir

622
00:24:46,990 --> 00:24:48,970
per kiek reikia visą sąrašą.

623
00:24:48,970 --> 00:24:51,890
Bet kas svarbiausia apie tai sujungti
procesas yra aš Palyginus šias poras

624
00:24:51,890 --> 00:24:53,460
elementų.

625
00:24:53,460 --> 00:24:57,270
Iš dešinės pusės ir iš kairės
pusė, aš nė karto atsitraukia.

626
00:24:57,270 --> 00:25:00,570
>> Taigi sujungti pati imasi
ne daugiau kaip n žingsnių.

627
00:25:00,570 --> 00:25:03,250
Ir kiek kartų padarė Turiu
padaryti, kad sujungus?

628
00:25:03,250 --> 00:25:07,150
Na, ne daugiau nei n, ir mes tiesiog
pamatė, kad su galutiniu suliejimo.

629
00:25:07,150 --> 00:25:13,120
Ir todėl, jei jūs ką nors, kad mano
log n žingsnių n kartų, arba atvirkščiai,

630
00:25:13,120 --> 00:25:15,210
jis ketina duoti mums n kartų log n.

631
00:25:15,210 --> 00:25:16,310
>> Ir kodėl tai yra geriau?

632
00:25:16,310 --> 00:25:19,600
Na, jei mes jau žinome, kad žurnalą
n yra geriau nei n - tiesa?

633
00:25:19,600 --> 00:25:22,590
Mes matėme dvejetainėje paiešką, telefono knyga
Pavyzdžiui, log n tikrai buvo

634
00:25:22,590 --> 00:25:23,760
geriau nei tiesinis.

635
00:25:23,760 --> 00:25:28,420
Taigi, tai reiškia n kartų log n yra
tikrai geriau nei n kartų kitą

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

637
00:25:30,390 --> 00:25:32,400
Ir tai, ką mes galiausiai jaustis.

638
00:25:32,400 --> 00:25:34,928
>> Taigi didelis audringi plojimai, jei
galėtume, šių vaikinai.

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

640
00:25:38,920 --> 00:25:41,550
>> Davidas Malan: Ir jūsų atsisveikinimo dovanos -
galite išsaugoti numerius,

641
00:25:41,550 --> 00:25:44,010
jei norėtumėte.

642
00:25:44,010 --> 00:25:45,620
Ir tavo atsisveikinimo dovana, kaip įprasta.

643
00:25:45,620 --> 00:25:47,290
Oh, ir mes atsiųsime Jums
filmuota medžiaga Michelle.

644
00:25:47,290 --> 00:25:48,343
Ačiū.

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

646
00:25:49,250 --> 00:25:50,400
Padėti sau streso kamuolys.

647
00:25:50,400 --> 00:25:54,110
>> Ir leiskite man atsigriebti, tuo tarpu,
mūsų draugas Robas Bowden ir pasiūlyti

648
00:25:54,110 --> 00:25:59,520
šiek tiek kitoks požiūris į tai,
nes jūs galite galvoti apie tai

649
00:25:59,520 --> 00:26:01,280
veiksmai vyksta šiek tiek
kitaip.

650
00:26:01,280 --> 00:26:04,750
Tiesą sakant, steigti, kas Rob apie
parodyti mums, daroma prielaida, kad mes

651
00:26:04,750 --> 00:26:09,030
jau padaryta dalijant sudaro
didelis sąrašas į aštuonias mažų sąrašus,

652
00:26:09,030 --> 00:26:10,570
kiekvieno dydžio 1.

653
00:26:10,570 --> 00:26:13,350
>> Taigi, mes keičiasi pseudocode
truputį tik rūšiuoti gauti ne

654
00:26:13,350 --> 00:26:15,320
pagrindinė idėja, kaip sujungti darbus.

655
00:26:15,320 --> 00:26:17,600
Bet važiavimo laikas, ką
jis apie tai dar

656
00:26:17,600 --> 00:26:19,110
bus tas pats.

657
00:26:19,110 --> 00:26:23,540
Ir vėl steigti čia yra tai, kad jis
prasidėjo aštuonių sąrašus dydis 1.

658
00:26:23,540 --> 00:26:27,730
Taigi jūs praleidote dalį, kur jis
iš tikrųjų padaryta log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
dalijant iš įvesties.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO PLAYBACK]

661
00:26:32,120 --> 00:26:33,615
>> -Štai ir viskas už žingsnio.

662
00:26:33,615 --> 00:26:38,270
Dėl antro žingsnio, pakartotinai
sujungti porų sąrašus.

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

664
00:26:39,210 --> 00:26:41,270
Tik garso artėja
iš mano kompiuterio.

665
00:26:41,270 --> 00:26:42,520
Pabandykime dar kartą.

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

667
00:26:45,330 --> 00:26:48,310
>> -Tiesiog savavališkai pasirinkti, kuris -
dabar mes turime keturis sąrašus.

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

669
00:26:51,590 --> 00:26:52,120
Sužinokite anksčiau.

670
00:26:52,120 --> 00:26:53,040
>> Davidas Malan: Čia mes eiti.

671
00:26:53,040 --> 00:27:00,510
>> -Sujungimas 108 ir 15 straipsnius, mes galų
su sąrašas 15 108.

672
00:27:00,510 --> 00:27:07,170
Sujungus 50 ir 4, mes
baigti su 4, 50.

673
00:27:07,170 --> 00:27:12,990
Sujungimas 8 ir 42 straipsnius, mes
baigti su 8, 42.

674
00:27:12,990 --> 00:27:19,970
Ir sujungti 23 ir 16 straipsniuose, mes
baigti su 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Dabar visi mūsų sąrašuose yra 2 dydžio.

676
00:27:23,270 --> 00:27:26,690
Atkreipkite dėmesį, kad kiekviena
keturi sąrašai yra rūšiuojama.

677
00:27:26,690 --> 00:27:29,450
Taigi, mes galime pradėti sujungti
porų sąrašus dar kartą.

678
00:27:29,450 --> 00:27:38,420
Sujungus 15 ir 108 4 ir 50, mes
pirmiausia reikia 4, tada 15, tada

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

680
00:27:41,500 --> 00:27:50,610
Sujungimas 8, 42 ir 16, 23, mes pirmiausia reikia
8, tada 16, tada 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Taigi dabar mes turime tik du sąrašus dydžio
4, iš kurių kiekvienas yra rūšiuojama.

683
00:27:57,600 --> 00:28:01,170
Taigi dabar mes sujungti šiuos du sąrašus.

684
00:28:01,170 --> 00:28:11,835
Pirma, mes imame 4, tada mes
8, tada mes priimsime 15, tada 16, tada

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

686
00:28:19,456 --> 00:28:19,872
>> [PABAIGA VIDEO PLAYBACK]

687
00:28:19,872 --> 00:28:23,430
>> Davidas Malan: Vėlgi, pranešimas, jis niekada
palietė tam tikrą taurę daugiau nei vieną kartą

688
00:28:23,430 --> 00:28:24,860
po priekį už jos ribų.

689
00:28:24,860 --> 00:28:26,200
Taigi jis niekada kartoti.

690
00:28:26,200 --> 00:28:29,850
Taigi, jis visada juda į šoną,
ir tai, kur mes turime mūsų n.

691
00:28:29,850 --> 00:28:33,290
>> Kodėl gi ne leiskite man atsigriebti vieną animaciją
kad mes matėme anksčiau, bet šį kartą

692
00:28:33,290 --> 00:28:35,110
skirta tik suliejimo rūšiuoti.

693
00:28:35,110 --> 00:28:38,030
Leiskite man eiti į priekį ir priartinti
ir apie tai čia.

694
00:28:38,030 --> 00:28:42,530
Pirmiausia leiskite man pasirinkti atsitiktinę įvestį,
paaštrins, ir jūs galite rūšiuoti pamatyti

695
00:28:42,530 --> 00:28:46,600
ką mes paėmė už suteiktas, anksčiau,
sujungti tarsi iš tikrųjų daro.

696
00:28:46,600 --> 00:28:50,330
>> Taigi, pastebėsite, kad jūs gaunate šias puses arba
šie ketvirčiais arba jų aštuonių iš

697
00:28:50,330 --> 00:28:53,140
problema, kad visi staiga
pradėti imtis geros formos.

698
00:28:53,140 --> 00:28:57,070
Ir galiausiai, kaip matote ne
labai pabaiga, kad bam

699
00:28:57,070 --> 00:28:58,860
viskas sujungta kartu.

700
00:28:58,860 --> 00:29:01,690
>> Taigi tai yra tik trijų skirtingų
įgauna tą pačią idėją.

701
00:29:01,690 --> 00:29:05,980
Bet svarbiausia įžvalga, kaip ir atskirties
ir užkariauti pačioje pirmoje klasėje,

702
00:29:05,980 --> 00:29:10,640
buvo ta, kad mes nusprendėme kažkaip padalinti
į kažką didelis, į problema

703
00:29:10,640 --> 00:29:14,760
kažkas tarsi identiški dvasia,
bet mažesni ir mažesni ir mažesni

704
00:29:14,760 --> 00:29:15,660
ir mažesnis.

705
00:29:15,660 --> 00:29:18,420
>> Dabar dar vienas įdomus būdas rūšiuoti mano,
apie tai, nors tai nėra

706
00:29:18,420 --> 00:29:20,520
norėčiau duoti jums tą patį intuityvus
supratimas, yra

707
00:29:20,520 --> 00:29:21,640
taip animacija.

708
00:29:21,640 --> 00:29:25,400
Taigi tai yra vaizdo įdėti ką nors kartu
kad susijęs skiriasi

709
00:29:25,400 --> 00:29:29,970
garsai, turintys įvairių operacijų
įterpimo rūšiuoti, už suliejimo rūšiuoti, ir

710
00:29:29,970 --> 00:29:31,150
dėl kitų pora.

711
00:29:31,150 --> 00:29:32,330
Taigi vienu metu, aš ketina hit Atkurti.

712
00:29:32,330 --> 00:29:33,600
Tai apie minučių ilgio.

713
00:29:33,600 --> 00:29:37,410
Ir net jei jūs vis dar galite pamatyti
modeliai vyksta, šiuo metu galite

714
00:29:37,410 --> 00:29:41,420
taip pat išgirsti, kaip šie algoritmai
atlieka skirtingai ir

715
00:29:41,420 --> 00:29:43,950
šiek tiek skirtingi modeliai.

716
00:29:43,950 --> 00:29:45,830
>> Tai įterpimo rūšiuoti.

717
00:29:45,830 --> 00:29:50,400
>> [TONES PLAYING]

718
00:29:50,400 --> 00:29:52,400
>> Davidas Malan: Jis vėl bando
įterpti kiekvieną elementą

719
00:29:52,400 --> 00:29:52,900
į kur jis priklauso.

720
00:29:52,900 --> 00:29:54,628
Tai burbulas rūšiuoti.

721
00:29:54,628 --> 00:30:10,097
>> [TONES PLAYING]

722
00:30:10,097 --> 00:30:13,630
>> Davidas Malan: Ir jūs galite rūšiuoti jaustis
kaip santykinai mažai dirbti jis daro

723
00:30:13,630 --> 00:30:15,834
ant kiekvieno žingsnio.

724
00:30:15,834 --> 00:30:20,470
Tai, ką Monotoniška skamba.

725
00:30:20,470 --> 00:30:21,472
>> [TONES PLAYING]

726
00:30:21,472 --> 00:30:25,222
>> Davidas Malan: Tai pasirinkimas rūšiuoti,
kur mes pasirinkite elementą norime pagal

727
00:30:25,222 --> 00:30:28,845
išgyvena vėl ir vėl ir vėl
ir pradėti jį iš pradžių.

728
00:30:28,845 --> 00:30:37,674
>> [TONES PLAYING]

729
00:30:37,674 --> 00:30:43,970
>> Davidas Malan: tai sujungti rūšiuoti, kuris
tikrai galite pradėti jaustis.

730
00:30:43,970 --> 00:30:51,810
>> [TONES PLAYING]

731
00:30:51,810 --> 00:30:54,770
>> [Juokas]

732
00:30:54,770 --> 00:30:58,395
>> Davidas Malan: Kažkas vadinamas gnome
rūšiuoti, kurį mes ne pažvelgė.

733
00:30:58,395 --> 00:31:13,630
>> [TONES PLAYING]

734
00:31:13,630 --> 00:31:17,910
>> Davidas Malan: Taigi leiskite man pamatyti, kad dabar,
išsiblaškęs, kaip jums tikiuosi, yra iš

735
00:31:17,910 --> 00:31:21,110
muzikos, jei aš galiu slydimo mažai
tiek matematikos čia.

736
00:31:21,110 --> 00:31:24,850
Taigi, čia yra ketvirtas būdas, kad mes galime
galvoti apie tai, ką reiškia šie

737
00:31:24,850 --> 00:31:29,210
funkcijas, kurios bus greičiau nei tie,
kad mes matėme anksčiau.

738
00:31:29,210 --> 00:31:32,470
Ir jei jūs dar tuo metu iš
matematika fone, jūs

739
00:31:32,470 --> 00:31:36,030
iš tikrųjų žino, galbūt jau, kad jūs
gali slap terminą nuo šio metodo -

740
00:31:36,030 --> 00:31:40,400
būtent rekursija, funkcija
kad kažkaip save vadina.

741
00:31:40,400 --> 00:31:44,780
>> Ir vėl priminti, kad suliejimo rūšiuoti
Pseudocode buvo pakartotinė ta prasme,

742
00:31:44,780 --> 00:31:48,460
kad vienas iš Merge sort žingsnius
buvo paraginti rūšiuoti -

743
00:31:48,460 --> 00:31:49,740
tai yra pati.

744
00:31:49,740 --> 00:31:52,480
Bet, laimei, nes mes nuolat
raginama rūšiuoti, arba sujungti rūšiuoti,

745
00:31:52,480 --> 00:31:55,880
Tiksliau, į mažesnes
ir mažesnių sąrašas, mes galiausiai

746
00:31:55,880 --> 00:32:00,005
dugną dėka ką mes vadiname
bazinį scenarijų, sunkiai koduojamų atvejis,

747
00:32:00,005 --> 00:32:04,270
sakė, kad jei sąrašas yra mažas, mažiau nei 2
Tokiu atveju, tiesiog grįžti iš karto.

748
00:32:04,270 --> 00:32:07,550
Jei mes ne turėti, kad ypatingas atvejis,
algoritmas niekada iš apačios,

749
00:32:07,550 --> 00:32:11,010
ir jūs iš tikrųjų gauti į
begalinis ciklas tikrai amžinai.

750
00:32:11,010 --> 00:32:14,330
>> Bet tarkime, kad mes norėjome dabar įdėti
keletas patarimų, tai numeriai, vėlgi, naudojant n

751
00:32:14,330 --> 00:32:15,660
kaip įėjimo dydžio.

752
00:32:15,660 --> 00:32:18,680
Ir aš norėjau paklausti, kas
bendras laikas dalyvauja

753
00:32:18,680 --> 00:32:19,800
veikia suliejimo rūšiuoti?

754
00:32:19,800 --> 00:32:22,960
Ar apskritai kas
jos sąnaudos metu?

755
00:32:22,960 --> 00:32:24,730
>> Na tai gana lengva pamatuoti.

756
00:32:24,730 --> 00:32:29,010
Jei n yra mažesnis nei 2 metu dalyvauja
rūšiavimo n elementų,

757
00:32:29,010 --> 00:32:30,480
kur n yra 2, yra 0.

758
00:32:30,480 --> 00:32:31,410
Kadangi mes tiesiog grįžti.

759
00:32:31,410 --> 00:32:32,510
Nėra nuveikti.

760
00:32:32,510 --> 00:32:35,660
Dabar tikriausiai, o gal tai vienas žingsnis ar du
žingsniai išsiaiškinti sumą

761
00:32:35,660 --> 00:32:38,420
dirbti, bet tai pakankamai arti 0, kad
Aš tik ketina pasakyti "ne" darbas

762
00:32:38,420 --> 00:32:40,940
būtinas, jei sąrašas yra toks mažas,
būti neįdomu.

763
00:32:40,940 --> 00:32:42,580
>> Tačiau šis atvejis įdomus.

764
00:32:42,580 --> 00:32:47,320
Rekursywny byla buvo filialas
Pseudocode tai sakė kitur, tarsi

765
00:32:47,320 --> 00:32:52,000
kairė pusė, rūšiuoti teisė
pusę, sujungti dvi dalis.

766
00:32:52,000 --> 00:32:55,530
Dabar kodėl ši išraiška
atstovauja tai sąskaita?

767
00:32:55,530 --> 00:32:58,690
Na, T n tiesiog reiškia,
laikas rūšiuoti n elementų.

768
00:32:58,690 --> 00:33:03,070
Ir tada dešinėje pusėje
lygybės ženklą ten, n T suskirstyti

769
00:33:03,070 --> 00:33:06,600
pagal 2 nuoroda į kokia kaina?

770
00:33:06,600 --> 00:33:07,570
Rūšiavimas kairę pusę.

771
00:33:07,570 --> 00:33:10,990
Kitas T n dalijamas iš 2
matyt, nuoroda į išlaidų

772
00:33:10,990 --> 00:33:12,390
rūšiuoti tinkamą pusę.

773
00:33:12,390 --> 00:33:14,590
>> Ir tada plius n?

774
00:33:14,590 --> 00:33:15,420
Ar sujungus.

775
00:33:15,420 --> 00:33:19,120
Nes jei jūs turite du sąrašus, vienas iš
dydis n per 2 ir kitas dydis n

776
00:33:19,120 --> 00:33:22,580
per 2, turite iš esmės paliesti
kiekvienas iš šių elementų, kaip Rob

777
00:33:22,580 --> 00:33:24,990
palietė kiekvieną puodeliai, ir tik
kaip pažymėjome kiekviename

778
00:33:24,990 --> 00:33:26,310
savanoriai scenoje.

779
00:33:26,310 --> 00:33:28,790
Taigi n yra sujungti sąskaita.

780
00:33:28,790 --> 00:33:31,780
>> Dabar, deja, ši formulė
taip pat pati pakartotinė.

781
00:33:31,780 --> 00:33:36,390
Taigi, jei uždavė klausimą, jei n yra, tarkim,
16, jei yra 16 žmonių scenoje

782
00:33:36,390 --> 00:33:40,670
arba 16 puodeliai vaizdo, kiek iš viso
žingsniai užtrunka juos surūšiuoti

783
00:33:40,670 --> 00:33:41,550
su suliejimo rūšiuoti?

784
00:33:41,550 --> 00:33:45,790
Tai iš tikrųjų nėra akivaizdu, atsakymas,
nes dabar jūs turite rūšiuoti

785
00:33:45,790 --> 00:33:48,500
rekursyviai atsakyti į šį formulę.

786
00:33:48,500 --> 00:33:51,190
>> Bet tai gerai, nes leiskite man pasiūlyti
kad mes atlikite šiuos veiksmus.

787
00:33:51,190 --> 00:33:56,670
Šiuo metu dalyvauja rūšiuoti 16 žmonių arba
16 puodeliai ketina atstovauti

788
00:33:56,670 --> 00:33:58,020
paprastai kaip T 16.

789
00:33:58,020 --> 00:34:01,400
Bet tai lygu pagal mūsų
Ankstesnis formulė, 2 kartus suma

790
00:34:01,400 --> 00:34:04,780
laiko užtrunka rūšiuoti
8 puodeliai plius 16.

791
00:34:04,780 --> 00:34:08,590
Ir vėl, plius 16 yra laikas sujungti,
ir du kartus T 8 yra

792
00:34:08,590 --> 00:34:10,790
laikas rūšiuoti kairę pusę ir į dešinę pusę.

793
00:34:10,790 --> 00:34:11,989
>> Bet vėl, tai nėra pakankamai.

794
00:34:11,989 --> 00:34:13,210
Mes turime pasinerti giliau.

795
00:34:13,210 --> 00:34:16,409
Tai reiškia, kad mes turime atsakyti
klausimas, kas tai yra "T 8?

796
00:34:16,409 --> 00:34:19,610
Na T 8 yra tik 2
kartų T 4 plius 8.

797
00:34:19,610 --> 00:34:20,520
Na, kas T 4?

798
00:34:20,520 --> 00:34:23,780
T 4 yra tik 2 kartus t 2 plius 4.

799
00:34:23,780 --> 00:34:25,489
Na, kas T 2?

800
00:34:25,489 --> 00:34:29,030
T 2 "yra vos 2 kartus T 1 plius 2.

801
00:34:29,030 --> 00:34:31,940
>> Ir vėl mes natūra gauti
įstrigo šio ciklo.

802
00:34:31,940 --> 00:34:34,790
Bet tai apie pataikyti, kad
vadinamasis bazinį scenarijų.

803
00:34:34,790 --> 00:34:37,310
Nes tai, kas yra T 1, tai mes reikalauti?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Taigi dabar, pagaliau, galime dirbti atgal.

806
00:34:39,730 --> 00:34:44,290
>> Jei T 1 yra 0, aš dabar gali eiti atgal dar vieną
išsirikiuoti šis vaikinas čia, ir aš galiu

807
00:34:44,290 --> 00:34:46,330
prijunkite 0, kai t 1.

808
00:34:46,330 --> 00:34:51,770
Taigi, tai reiškia, kad ji yra lygi 2 kartus nulis,
kitaip žinomas kaip 0, plius 2.

809
00:34:51,770 --> 00:34:53,739
Ir kad visa išraiška 2.

810
00:34:53,739 --> 00:34:58,740
>> Dabar, jei aš su 2 T, kurio atsakymas
yra 2, prijunkite jį prie vidurio linijos, T

811
00:34:58,740 --> 00:35:02,740
4, kuris suteikia man 2 kartus
2 plius 4, todėl 8.

812
00:35:02,740 --> 00:35:07,080
Jei aš tada prijungti 8 iki ankstesnio
linija, kuri suteikia man 2 kartus 8, 16.

813
00:35:07,080 --> 00:35:12,470
Ir jei mes tęskite, kad su
24, pridedant 16, mes pagaliau gauti

814
00:35:12,470 --> 00:35:13,820
vertė 64.

815
00:35:13,820 --> 00:35:18,480
>> Dabar, kad ir pati tarsi kalba
nieko n žymėjimą,

816
00:35:18,480 --> 00:35:20,700
Didelės O, omega, kad mes
buvo kalbama apie.

817
00:35:20,700 --> 00:35:24,890
Tačiau paaiškėja, kad 64 yra iš tiesų
16, įėjimas, dydis,

818
00:35:24,890 --> 00:35:27,110
prisijungti 16 2 bazę.

819
00:35:27,110 --> 00:35:30,200
Ir jei tai yra šiek tiek susipažinę, tiesiog
prisiminkite, ir jis bus grįžti

820
00:35:30,200 --> 00:35:30,700
jums galų gale.

821
00:35:30,700 --> 00:35:33,775
Jei tai žurnalas bazė 2, tai kaip 2
pakeltas, kas suteikia jums 16?

822
00:35:33,775 --> 00:35:36,380
O, tai 4, todėl 16 kartų 4.

823
00:35:36,380 --> 00:35:39,380
>> Ir vėl, tai ne baisi, jei tai
yra tarsi miglotos atminties dabar.

824
00:35:39,380 --> 00:35:43,720
Bet dabar, imtis tikėjimo
kad 16 log 16 vertė yra 64.

825
00:35:43,720 --> 00:35:46,590
Ir taip iš tiesų, su šia paprasta sveiko proto
patikrinti, mes patvirtino -

826
00:35:46,590 --> 00:35:48,250
bet neįrodė oficialiai -

827
00:35:48,250 --> 00:35:52,800
kad veikimo laikas suliejimą
rūšiuoti yra iš tiesų n log n.

828
00:35:52,800 --> 00:35:53,790
>> Taigi nėra blogai.

829
00:35:53,790 --> 00:35:57,260
Tai tikrai geriau nei
algoritmai mes matėme iki šiol, ir

830
00:35:57,260 --> 00:36:00,710
tai todėl, kad mes pagausėtų, viena,
technika vadinama rekursija.

831
00:36:00,710 --> 00:36:03,880
Bet įdomesnis nei, kad
sąvoka dalijant ir užkariauja.

832
00:36:03,880 --> 00:36:07,460
Vėlgi, tikrai savaitę 0 stuff, kad
net ir dabar yra pasikartojimo

833
00:36:07,460 --> 00:36:08,740
daugiau įtikinamų būdu.

834
00:36:08,740 --> 00:36:11,750
>> Dabar įdomus mažai pratimų, jei jūs
niekada tai padarė - ir jūs tikriausiai

835
00:36:11,750 --> 00:36:14,660
neturės, nes tarsi normalu
žmonių neturi galvoti kaip tai padaryti.

836
00:36:14,660 --> 00:36:20,650
Bet jei aš einu į google.com ir, jei
Noriu sužinoti ką nors apie

837
00:36:20,650 --> 00:36:22,356
rekursija, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Juokas]

840
00:36:29,058 --> 00:36:32,030
[Daugiau juokas]

841
00:36:32,030 --> 00:36:33,385
Davidas Malan: Blogas pokštas lėtai plisti.

842
00:36:33,385 --> 00:36:34,450
[Juokas]

843
00:36:34,450 --> 00:36:36,970
Davidas Malan: Tik tuo atveju, tai ten.

844
00:36:36,970 --> 00:36:38,710
Aš ne aiškiai tai negerai,
ir ten pokštas.

845
00:36:38,710 --> 00:36:40,810
Gerai.

846
00:36:40,810 --> 00:36:42,950
Paaiškinti žmonėms, šalia tavęs, jei
ji ne visai paspaudėte tik dar.

847
00:36:42,950 --> 00:36:47,650
Bet rekursija, apskritai, reiškia
su funkcija telefono proceso

848
00:36:47,650 --> 00:36:51,430
pati, ar apskritai dalijant
problema į kažką, kad gali būti

849
00:36:51,430 --> 00:36:56,220
išspręsta dalimis sprendžiant identiškas
atstovas problemos.

850
00:36:56,220 --> 00:36:58,400
>> Na, tegul perjungti pavaras
tik akimirką.

851
00:36:58,400 --> 00:37:00,840
Mes norėtume užbaigti dėl tam tikrų cliffhangers,
todėl galime pradėti kurti

852
00:37:00,840 --> 00:37:05,870
etapas, keletą minučių,
dėl labai paprastą idėją -

853
00:37:05,870 --> 00:37:07,620
kad keičiant du elementus, tiesa?

854
00:37:07,620 --> 00:37:10,040
Visi šie algoritmai mes jau
kalbame apie pastaruosius porą

855
00:37:10,040 --> 00:37:12,420
paskaitos įtraukti kai kurie
rūšiuoti Swapping.

856
00:37:12,420 --> 00:37:14,630
Šiandien ji buvo regimos juos gauti
iki iš savo kėdės ir

857
00:37:14,630 --> 00:37:18,570
vaikščioti aplink, bet kodu, mes norėtume
tiesiog elementą iš vieno masyvo

858
00:37:18,570 --> 00:37:20,370
ir pop jį į kitą.

859
00:37:20,370 --> 00:37:21,880
>> Taigi, kaip mes eiti apie tai daro?

860
00:37:21,880 --> 00:37:24,850
Na, leiskite man eiti į priekį ir rašyti
Trumpa programa čia.

861
00:37:24,850 --> 00:37:31,600
Aš ruošiuosi eiti į priekį ir daryti
tai kaip toliau.

862
00:37:31,600 --> 00:37:33,910
Tegul tai vadina -

863
00:37:33,910 --> 00:37:38,070
ką mes norime paraginti šį vieną?

864
00:37:38,070 --> 00:37:38,650
>> Tiesą sakant, ne.

865
00:37:38,650 --> 00:37:39,420
Leiskite man atgal.

866
00:37:39,420 --> 00:37:41,220
Aš nenoriu to daryti
Įspūdingos filmą dar.

867
00:37:41,220 --> 00:37:42,270
Tai bus sugadinti įdomus.

868
00:37:42,270 --> 00:37:43,600
Leiskite tai padaryti vietoj.

869
00:37:43,600 --> 00:37:47,430
>> Tarkime, kad aš noriu rašyti mažai
programa ir kad dabar apima ši

870
00:37:47,430 --> 00:37:48,700
idėja rekursijos.

871
00:37:48,700 --> 00:37:50,370
I rūšies gavo prieš save ten.

872
00:37:50,370 --> 00:37:51,420
Aš ruošiuosi atlikite šiuos veiksmus.

873
00:37:51,420 --> 00:38:00,220
>> Pirma, greitai apima standartinės io.h,
taip pat iš cs50.h. apima

874
00:38:00,220 --> 00:38:03,200
Ir tada aš ruošiuosi eiti į priekį
ir paskelbti int main negaliojančiu

875
00:38:03,200 --> 00:38:04,360
įprastu būdu.

876
00:38:04,360 --> 00:38:07,920
Supratau, aš misnamed failą, todėl
leiskite man tiesiog pridėkite. c Papildomo čia taip

877
00:38:07,920 --> 00:38:09,510
kad mes galime sudaryti tinkamai.

878
00:38:09,510 --> 00:38:10,970
Pradėti šią funkciją išjungti.

879
00:38:10,970 --> 00:38:13,290
>> Ir funkcija noriu rašyti, gana
tiesiog, yra vienas, kad prašo

880
00:38:13,290 --> 00:38:16,210
vartotojas už skaičių ir tada išauga iki
visi įmonių tarpusavio, kad numeriai

881
00:38:16,210 --> 00:38:19,920
skaičius ir, tarkim, 0.

882
00:38:19,920 --> 00:38:22,510
Taigi, pirmiausia aš ruošiuosi eiti į priekį
ir paskelbti int n.

883
00:38:22,510 --> 00:38:24,760
Tada aš nukopijuoti tam tikrą kodą, kad
mes naudojame tam tikrą laiką.

884
00:38:24,760 --> 00:38:26,660
Nors kažkas yra tiesa.

885
00:38:26,660 --> 00:38:28,000
Aš sugrįšiu į tą, akimirką.

886
00:38:28,000 --> 00:38:29,010
>> Ką norite daryti?

887
00:38:29,010 --> 00:38:33,460
Noriu pasakyti printf teigiamas
sveikasis skaičius prašom.

888
00:38:33,460 --> 00:38:36,130
Ir tada aš ruošiuosi
pasakyti n gauna gauti int.

889
00:38:36,130 --> 00:38:38,800
Taigi dar kartą, kai Standartiniai kodas
kad mes naudojamas anksčiau.

890
00:38:38,800 --> 00:38:40,810
Ir aš ruošiuosi tai padaryti
o n yra mažesnis nei 1.

891
00:38:40,810 --> 00:38:44,120
Taigi tai bus užtikrinta, kad vartotojo
suteikia man teigiamą sveikąjį skaičių.

892
00:38:44,120 --> 00:38:45,490
>> Ir dabar aš ruošiuosi daryti toliau.

893
00:38:45,490 --> 00:38:51,020
Noriu pridėti visus numerius
nuo 1 iki ir n-arba 0 ir n

894
00:38:51,020 --> 00:38:52,570
analogiškai, jei norite gauti bendrą sumą.

895
00:38:52,570 --> 00:38:55,100
Taigi didelis sigma simbolis
kad jums gali prisiminti.

896
00:38:55,100 --> 00:38:59,050
Taigi, aš ruošiuosi tai padaryti pirmą skambučiams
funkcija vadinama sigma,

897
00:38:59,050 --> 00:39:06,030
perduoti ją į n, ir tada aš ruošiuosi
pasakyti printf, atsakymas yra teisę ten.

898
00:39:06,030 --> 00:39:08,180
>> Taigi trumpai tariant, man ir
int nuo naudotojo.

899
00:39:08,180 --> 00:39:09,280
Aš užtikrinti, kad ji yra teigiamas.

900
00:39:09,280 --> 00:39:12,700
Aš pareiškiu, kintamasis vadinamas atsakymas
tipas int ir laikyti jį grąžinti

901
00:39:12,700 --> 00:39:15,610
vertė sigma, einančios n kaip įvestį.

902
00:39:15,610 --> 00:39:17,060
Ir tada aš atsispausdinti šį atsakymą.

903
00:39:17,060 --> 00:39:19,550
>> Deja, nors sigma skamba
kaip kažkas, kad gali būti

904
00:39:19,550 --> 00:39:24,040
math.h failas, jo deklaracija,
tai tikrai ne.

905
00:39:24,040 --> 00:39:24,690
Taigi, kad viskas OK.

906
00:39:24,690 --> 00:39:26,170
Galiu įgyvendinti šį save.

907
00:39:26,170 --> 00:39:29,160
Aš ruošiuosi įgyvendinti funkcija vadinama
sigma, ir ji ketina imtis

908
00:39:29,160 --> 00:39:29,900
parametras -

909
00:39:29,900 --> 00:39:32,100
galime tik jį vadiname m, tiesiog
todėl skiriasi.

910
00:39:32,100 --> 00:39:35,910
Ir tada čia aš ruošiuosi pasakyti,
Na, jei m yra mažesnis nei 1 - tai

911
00:39:35,910 --> 00:39:38,180
labai neįdomu programą.

912
00:39:38,180 --> 00:39:41,700
Taigi, aš ruošiuosi eiti į priekį ir
nedelsiant grąžinti 0.

913
00:39:41,700 --> 00:39:45,920
Jis tiesiog nėra prasmės pridėti iki visų
tarp 1 ir M Jei m numeriai

914
00:39:45,920 --> 00:39:48,470
pati 0 arba neigiamas.

915
00:39:48,470 --> 00:39:50,900
>> Ir tada aš ruošiuosi eiti į priekį
ir tai labai iteracijų.

916
00:39:50,900 --> 00:39:53,090
Aš ruošiuosi padaryti šį senosios mokyklos rūšiuoti,
ir aš ruošiuosi eiti į priekį

917
00:39:53,090 --> 00:39:57,150
ir pasakyti, kad aš ruošiuosi
deklaruoti sumą 0.

918
00:39:57,150 --> 00:39:59,630
Tada aš ruošiuosi
už linijos int -

919
00:39:59,630 --> 00:40:02,820
ir leiskite man tai padaryti geriau atitiktų mūsų
paskirstymo kodas, todėl jūs turite kopiją

920
00:40:02,820 --> 00:40:07,500
namuose. int i gauna 1 m iki
i yra mažesnė arba lygi m.

921
00:40:07,500 --> 00:40:09,430
i plius plius.

922
00:40:09,430 --> 00:40:11,430
Ir tada viduje tai už linijos -

923
00:40:11,430 --> 00:40:12,440
Mes beveik ten -

924
00:40:12,440 --> 00:40:15,810
suma gauna sumą, taip pat 1.

925
00:40:15,810 --> 00:40:17,670
Ir tada aš ruošiuosi grįžti sumą.

926
00:40:17,670 --> 00:40:19,420
>> Taigi aš tai greitai,
visai tiesa.

927
00:40:19,420 --> 00:40:22,775
Bet vėl, pagrindinė funkcija yra gana
paprasta, grindžiamas kodą mes

928
00:40:22,775 --> 00:40:23,190
parašyta iki šiol.

929
00:40:23,190 --> 00:40:25,610
Naudoja dvigubą kilpą gauti teigiami
int nuo naudotojo.

930
00:40:25,610 --> 00:40:29,870
Tada aš praeiti int į naują funkciją
vadinama sigma, vadindami jį, vėlgi, n.

931
00:40:29,870 --> 00:40:33,100
Ir aš laikyti sugrįžimo vertę, atsakymas
iš juodosios dėžės metu

932
00:40:33,100 --> 00:40:35,460
žinomas kaip sigma, kad kintamasis
vadinamas atsakymas.

933
00:40:35,460 --> 00:40:36,580
Tada aš spausdinti.

934
00:40:36,580 --> 00:40:39,090
>> Jei mes dabar tęsti istoriją,
kaip yra sigma įgyvendinti?

935
00:40:39,090 --> 00:40:40,840
Siūlau įgyvendinti taip.

936
00:40:40,840 --> 00:40:43,560
Pirma, šiek tiek Klaidų tikrinimas
įsitikinti, kad vartotojo nėra

937
00:40:43,560 --> 00:40:46,480
Messing su manimi ir einančios
kai neigiamas arba 0 vertė.

938
00:40:46,480 --> 00:40:49,710
Tada aš pareiškiu, kintamasis vadinamas
Apibendrinant ir nustatykite 0.

939
00:40:49,710 --> 00:40:55,910
>> Ir dabar aš pradedu judėti iš I lygus
1 visą kelią iki ir įskaitant m,

940
00:40:55,910 --> 00:41:00,130
nes noriu įtraukti visus
skaičiai nuo vieno iki m imtinai.

941
00:41:00,130 --> 00:41:04,350
Ir viduje tai už linijos, aš tiesiog padaryti
suma gauna kokia ji yra dabar, plius

942
00:41:04,350 --> 00:41:08,900
I vertė.

943
00:41:08,900 --> 00:41:10,370
Plius i vertė.

944
00:41:10,370 --> 00:41:14,090
>> Kaip panaikinti, jei nemačiau tai
anksčiau, yra keletas sintaksinis cukrus

945
00:41:14,090 --> 00:41:14,870
šios eilutės.

946
00:41:14,870 --> 00:41:21,120
Galiu perrašyti kaip plius lygus i,
tik sutaupyti sau keletą klavišų

947
00:41:21,120 --> 00:41:22,570
ir atrodo šiek tiek aušintuvas.

948
00:41:22,570 --> 00:41:23,140
Bet tai ir viskas.

949
00:41:23,140 --> 00:41:24,660
Tai funkciškai tas pats.

950
00:41:24,660 --> 00:41:26,710
>> Deja, šis kodas ųjų
nesiruošia sudaryti dar.

951
00:41:26,710 --> 00:41:31,600
Jei aš paleisti, kad sigma 0, kaip am
Aš ketina gauti sušuko?

952
00:41:31,600 --> 00:41:33,473
Kas ji ketina nepatinka?

953
00:41:33,473 --> 00:41:35,740
>> Auditorija: [nesigirdi].

954
00:41:35,740 --> 00:41:37,800
>> Davidas Malan: Taip, aš nedeklaravo
iki viršuje, dešinėje funkcija?

955
00:41:37,800 --> 00:41:40,590
C rūšies kvailas, nes jis tik
ką pasakyti tai padaryti, ir jūs

956
00:41:40,590 --> 00:41:41,880
turite tai padaryti tokia tvarka.

957
00:41:41,880 --> 00:41:45,910
Ir todėl, jei aš paspauskite Enter čia, aš ruošiuosi
gauti apie sigma įspėjimas numanoma

958
00:41:45,910 --> 00:41:46,860
deklaracija.

959
00:41:46,860 --> 00:41:48,120
>> O ne problema.

960
00:41:48,120 --> 00:41:50,370
Galiu eiti į viršų, ir aš galiu
sako, viskas gerai, palauk.

961
00:41:50,370 --> 00:41:54,240
Sigma yra funkcija, kuri grąžina
int ir tikisi,

962
00:41:54,240 --> 00:41:56,620
int kaip pirkimo, kabliataškiu.

963
00:41:56,620 --> 00:41:59,550
Ar galėčiau įdėti visą funkciją
virš pagrindinis, bet apskritai, aš

964
00:41:59,550 --> 00:42:02,260
rekomenduojame prieš tai, nes tai
malonu visada pagrindinis viršuje tt

965
00:42:02,260 --> 00:42:06,310
galite pasinerti teisę ir žinoti, ką
programa daro skaitant pagrindinė sritis.

966
00:42:06,310 --> 00:42:07,930
>> Taigi dabar leiskite man išvalyti ekraną.

967
00:42:07,930 --> 00:42:09,330
Perdarytas sigma 0.

968
00:42:09,330 --> 00:42:10,340
Viskas atrodo patikrinti.

969
00:42:10,340 --> 00:42:11,970
Leiskite man paleisti sigma 0.

970
00:42:11,970 --> 00:42:12,770
Teigiamas kita.

971
00:42:12,770 --> 00:42:15,580
Aš duosiu jam numerį
3 keep it simple.

972
00:42:15,580 --> 00:42:18,710
Taigi, kad turėtų duoti man 3
plius 2 plius 1, taigi 6.

973
00:42:18,710 --> 00:42:20,750
Įveskite, ir iš tiesų aš gausiu 6.

974
00:42:20,750 --> 00:42:21,820
>> Galiu padaryti kažką daugiau -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Tiesiog kaip liestinė, aš ruošiuosi daryti
kažką juokinga kaip tikrai didelis

977
00:42:27,690 --> 00:42:30,375
skaičius, O, kad faktiškai dirbo -

978
00:42:30,375 --> 00:42:31,600
eh, aš nemanau, kad tai tiesa.

979
00:42:31,600 --> 00:42:32,810
Pažiūrėkime.

980
00:42:32,810 --> 00:42:34,060
Leiskite tikrai netvarka su juo.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Tai problema.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Kas vyksta?

985
00:42:44,970 --> 00:42:46,050
Kodas nėra taip blogai.

986
00:42:46,050 --> 00:42:48,470
Jis vis dar tiesinis.

987
00:42:48,470 --> 00:42:50,810
Švilpimas yra geras poveikis, nors.

988
00:42:50,810 --> 00:42:52,060
Kas vyksta?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Nežinote jei aš girdėjau jį.

991
00:42:55,620 --> 00:42:57,620
Taigi paaiškėja, - ir
tai kaip panaikinti.

992
00:42:57,620 --> 00:42:59,400
Tai ne core
idėja rekursijos.

993
00:42:59,400 --> 00:43:02,480
Pasirodo, nes aš bandau
sudaro tokį didelį skaičių, dauguma

994
00:43:02,480 --> 00:43:06,980
greičiausiai jis bus klaidingai
sprendimu C kaip nėra teigiamas skaičius,

995
00:43:06,980 --> 00:43:09,980
bet neigiamas skaičius.

996
00:43:09,980 --> 00:43:12,690
>> Mes ne kalbėjo apie tai, bet jis
Pasirodo, yra neigiami skaičiai

997
00:43:12,690 --> 00:43:14,210
į be pasaulio
su teigiamais skaičiais.

998
00:43:14,210 --> 00:43:16,290
Ir būdus, kuriais galite
sudaro neigiamą skaičių

999
00:43:16,290 --> 00:43:19,530
iš esmės yra, jūs naudojate vieną
Specialusis tiek nurodyti

1000
00:43:19,530 --> 00:43:20,400
teigiami per neigiamas.

1001
00:43:20,400 --> 00:43:22,950
Tai šiek tiek sudėtingesnis nei, kad
bet tai pagrindinė idėja.

1002
00:43:22,950 --> 00:43:26,740
>> Taigi, deja, jei C painu vieną
iš tų tikrųjų reiškia bitai,

1003
00:43:26,740 --> 00:43:30,790
Oh, tai yra neigiamas skaičius, mano kilpa
Čia, pavyzdžiui, iš tikrųjų niekada

1004
00:43:30,790 --> 00:43:31,740
ketina nutraukti.

1005
00:43:31,740 --> 00:43:33,850
Taigi, jei aš iš tikrųjų buvo spausdinti kažką
vėl ir vėl, mes norėtume

1006
00:43:33,850 --> 00:43:34,650
pamatyti visą partiją.

1007
00:43:34,650 --> 00:43:36,220
Bet vėl, tai be taško.

1008
00:43:36,220 --> 00:43:38,590
Tai tikrai tiesiog tarsi
intelektinės smalsumas, kad mes ateis

1009
00:43:38,590 --> 00:43:39,550
atgal į ilgainiui.

1010
00:43:39,550 --> 00:43:43,400
Bet dabar, tai yra teisinga
įgyvendinimas, jei mes manome, kad

1011
00:43:43,400 --> 00:43:45,970
vartotojo teiks Ints
kad tilptų Ints.

1012
00:43:45,970 --> 00:43:49,370
>> Bet aš teigia, kad šis kodas, tiesą sakant,
gali būti padaryta tiek daug paprastai.

1013
00:43:49,370 --> 00:43:54,060
Jei po ranka tikslas praeiti kelios
kaip m, pridėti visi

1014
00:43:54,060 --> 00:43:59,510
numeriai tarp jo ir 1 arba atvirkščiai
nuo 1 ir, galiu reikalauti

1015
00:43:59,510 --> 00:44:03,380
kad galiu pasiskolinti šią idėją, kad sujungti
rūšiuoti turėjo buvo atsižvelgiant problemų

1016
00:44:03,380 --> 00:44:05,660
tokio dydžio ir dalinant
į kažką mažesnio.

1017
00:44:05,660 --> 00:44:09,875
Gal ir ne pusė, bet mažesnis, tačiau
tipiniai pats.

1018
00:44:09,875 --> 00:44:12,130
Pati idėja, bet mažesnė problema.

1019
00:44:12,130 --> 00:44:15,470
>> Taigi, aš iš tikrųjų - leiskite man išsaugoti šį failą
su kitu versijos numerį.

1020
00:44:15,470 --> 00:44:17,670
Mes vadiname šią versiją
1 vietoj 0.

1021
00:44:17,670 --> 00:44:20,790
Ir galiu reikalauti, kad aš iš tikrųjų galite
reimplement šią rūšies

1022
00:44:20,790 --> 00:44:22,160
proto-lenkimo būdu.

1023
00:44:22,160 --> 00:44:23,710
>> Aš ruošiuosi palikti dalį jai pačiai.

1024
00:44:23,710 --> 00:44:27,710
Aš ruošiuosi pasakyti, jei m yra mažiau
nei ar net lygi 0 -

1025
00:44:27,710 --> 00:44:29,280
Aš tiesiog bus mažai
daugiau analinis šį kartą

1026
00:44:29,280 --> 00:44:30,520
su mano klaidų tikrinimas -

1027
00:44:30,520 --> 00:44:33,190
Aš ruošiuosi eiti į priekį ir grįžti 0.

1028
00:44:33,190 --> 00:44:34,490
Tai savavališkai.

1029
00:44:34,490 --> 00:44:37,500
Aš tiesiog nuspręsti, ar vartotojo
man duoda neigiamą skaičių, aš

1030
00:44:37,500 --> 00:44:41,490
grįžti 0, ir jie turėjo skaityti
dokumentacija labiau.

1031
00:44:41,490 --> 00:44:42,170
>> Kita -

1032
00:44:42,170 --> 00:44:44,070
pastebėsite, ką aš ruošiuosi daryti.

1033
00:44:44,070 --> 00:44:49,260
Kita aš grįžti m plius -

1034
00:44:49,260 --> 00:44:51,010
kas yra sigma M?

1035
00:44:51,010 --> 00:44:56,710
Na, sigma iš m plius m ± 1,
plius minus m 2 plius minus 3 m.

1036
00:44:56,710 --> 00:44:58,030
Aš nenoriu rašyti visi, kad iš.

1037
00:44:58,030 --> 00:44:59,120
Kodėl ne aš tiesiog kamuolio išmušimas iš rankų?

1038
00:44:59,120 --> 00:45:05,080
Rekursyviai vadina save su šiek tiek
mažesnė problema, kabliataškis,

1039
00:45:05,080 --> 00:45:06,840
ir vadina jį dieną?

1040
00:45:06,840 --> 00:45:07,040
>> Teisė?

1041
00:45:07,040 --> 00:45:10,980
Dabar čia taip pat galite jaustis ar nerimauti
kad tai yra begalinis ciklas, kad aš

1042
00:45:10,980 --> 00:45:15,450
skatina, kai aš įgyvendinant
sigma iškvietus sigma.

1043
00:45:15,450 --> 00:45:20,342
Bet tai visiškai gerai, nes aš
maniau priekį pridėta į kurias eilutes?

1044
00:45:20,342 --> 00:45:22,600
>> Auditorija: [nesigirdi].

1045
00:45:22,600 --> 00:45:25,430
>> Davidas Malan: 23 už, 26 kuri
mano, jei sąlyga.

1046
00:45:25,430 --> 00:45:28,390
Nes tai, kas yra malonu apie
atimtis čia, nes aš nuolat

1047
00:45:28,390 --> 00:45:31,180
dalijamos sigma mažesnių problemų, mažesnių
problemų, mažesnių - tai ne

1048
00:45:31,180 --> 00:45:31,870
pusė dydžio.

1049
00:45:31,870 --> 00:45:34,380
Tai tik kūdikis žingsnis mažesnis,
bet tai gerai.

1050
00:45:34,380 --> 00:45:38,050
Nes, galų gale, mes dirbti
mūsų kelią žemyn iki 1 arba 0.

1051
00:45:38,050 --> 00:45:41,630
Ir kai mes paspauskite 0, sigma nėra
ketinate skambinti save daugiau.

1052
00:45:41,630 --> 00:45:43,590
Ji ketina nedelsiant grąžinti 0.

1053
00:45:43,590 --> 00:45:47,960
>> Taigi poveikis, jei tarsi vėjas tai
iki savo mintis, yra įtraukti m plius

1054
00:45:47,960 --> 00:45:52,740
m, atėmus 1, plius minus 2 m, plius m atėmus
3, plius taškas, taškas, taškas, m, atėmus

1055
00:45:52,740 --> 00:45:57,820
m, galiausiai suteikia jums 0, ir
poveikis yra galiausiai pridėti visus

1056
00:45:57,820 --> 00:45:59,070
šie dalykai kartu.

1057
00:45:59,070 --> 00:46:02,380
Taigi, mes turime ne, su rekursija,
išspręsti problemą, kad mes

1058
00:46:02,380 --> 00:46:03,470
negalėjo išspręsti anksčiau.

1059
00:46:03,470 --> 00:46:06,840
Iš tiesų, portalo 0 to, ir kiekvienas
problema iki šiol buvo išsprendžiamas

1060
00:46:06,840 --> 00:46:09,980
tik su naudojate kilpomis arba kai
kilpos arba panašių stato.

1061
00:46:09,980 --> 00:46:13,150
>> Bet rekursija, aš Manyti, suteikia mums
kitaip galvoti apie

1062
00:46:13,150 --> 00:46:17,010
problemos, kurią, jei mes galime imtis
problema, padalinkite jį nuo kažko

1063
00:46:17,010 --> 00:46:22,340
šiek tiek didelis, į kažką šiek tiek
mažesnis, galiu reikalauti, kad mes galime ją išspręsti

1064
00:46:22,340 --> 00:46:26,040
galbūt šiek tiek daugiau elegantiškai požiūriu
konstrukcijos, su mažiau kodą,

1065
00:46:26,040 --> 00:46:30,980
o gal net spręsti problemas, kad būtų
būti sunkiau, nes mes galų gale

1066
00:46:30,980 --> 00:46:33,280
pamatyti, sprendžiant grynai keletą kartų.

1067
00:46:33,280 --> 00:46:35,980
>> Bet Įspūdingos filmą, kad aš
nori palikti mums buvo tai.

1068
00:46:35,980 --> 00:46:40,720
Leiskite man eiti į priekį ir atidaryti
iki failą iš -

1069
00:46:40,720 --> 00:46:44,300
Tiesą sakant, leiskite man eiti ir
tai padaryti labai greitai.

1070
00:46:44,300 --> 00:46:46,875
Leiskite man eiti į priekį ir pasiūlyti
taip.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Tarp šiandienos kodas yra šį failą čia.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Tai vienas čia noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Taigi tai yra kvailas mažai programa, kuri
Aš plakta kuri teigia, kad daryti

1076
00:47:06,260 --> 00:47:06,940
taip.

1077
00:47:06,940 --> 00:47:10,140
Iš esmės, ji pirmą kartą pareiškia,
LC vadinamas x ir priskiria jį

1078
00:47:10,140 --> 00:47:11,100
vertė 1.

1079
00:47:11,100 --> 00:47:13,520
Tada jis pareiškia, int y ir
jam priskiria reikšmę 2.

1080
00:47:13,520 --> 00:47:15,310
Tada jis spausdina, ką x ir y yra.

1081
00:47:15,310 --> 00:47:17,781
Tada ji sako, Swapping, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Tada ji teigia būti raginama funkciją
vadinama swap, einančios į x ir

1083
00:47:21,670 --> 00:47:24,290
m, idėja yra tai, kad tikiuosi
x ir y sugrįš

1084
00:47:24,290 --> 00:47:25,620
skirtingi, priešingai.

1085
00:47:25,620 --> 00:47:27,110
Tada ji teigia pavertė!

1086
00:47:27,110 --> 00:47:28,420
su šauktuku.

1087
00:47:28,420 --> 00:47:30,190
Tada jis spausdina x ir y.

1088
00:47:30,190 --> 00:47:33,480
>> Tačiau paaiškėja, kad tai labai
paprastas demonstravimo žemyn

1089
00:47:33,480 --> 00:47:35,570
čia iš tikrųjų yra klaidų.

1090
00:47:35,570 --> 00:47:38,870
Nors aš skelbiantis laikinas
kintama ir laikinai išleisti į

1091
00:47:38,870 --> 00:47:42,010
tai, tada aš perskirstymo
vertė b -

1092
00:47:42,010 --> 00:47:45,080
kurie jaučiasi suprantama, nes aš
išgelbėti iš TEMP kopiją.

1093
00:47:45,080 --> 00:47:48,410
Tada aš atnaujinti b, lygios
kokia buvo temp.

1094
00:47:48,410 --> 00:47:51,610
Šis lukštais žaidimas juda rūšiuoti
į B And B į naudojant šį

1095
00:47:51,610 --> 00:47:54,360
vidutinio Žmogus, vadinamas temperatūros jaučiasi
visiškai pagrįsta.

1096
00:47:54,360 --> 00:47:57,270
>> Bet aš teigia, kad kai aš paleisti šį
kodas, kaip aš tai padaryti dabar -

1097
00:47:57,270 --> 00:47:59,490
leiskite man eiti į priekį ir įklijuokite jį čia.

1098
00:47:59,490 --> 00:48:01,995
Aš vadinu tai noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Ir kaip rodo pavadinimas, tai nėra
bus teisinga programa.

1100
00:48:05,630 --> 00:48:09,460
Padaryti noswap. / Ne sukeisti.

1101
00:48:09,460 --> 00:48:12,110
x 1, y 2, Swapping, pavertė.

1102
00:48:12,110 --> 00:48:14,220
x 1, y 2.

1103
00:48:14,220 --> 00:48:16,920
Tai yra iš esmės neteisinga, net
nors tai atrodo puikiai

1104
00:48:16,920 --> 00:48:17,730
protingas man.

1105
00:48:17,730 --> 00:48:21,330
Ir yra priežastis, bet mes ne
ketina atskleisti priežastis, tik dar.

1106
00:48:21,330 --> 00:48:24,610
>> Nes dabar antrą Įspūdingos filmą norėjau
palikti jus su tai,

1107
00:48:24,610 --> 00:48:27,120
paskelbimas rūšių apie kuponų kodų.

1108
00:48:27,120 --> 00:48:31,590
Mūsų naujovės pavėluotą dienų šiemet
jau išprovokavo ne trivialus skaičius

1109
00:48:31,590 --> 00:48:33,830
klausimų, kuris buvo
nėra mūsų tikslas.

1110
00:48:33,830 --> 00:48:36,590
Šių kuponų kodų ketinimą,
kurią, jei jūs problemos dalis

1111
00:48:36,590 --> 00:48:39,850
nustatyti anksti, todėl gauti papildomą dieną,
buvo tikrai padėti vaikinai padėti

1112
00:48:39,850 --> 00:48:42,420
sau pradėti anksti, rūšiuoti
apie kurį skatinamųjų jums.

1113
00:48:42,420 --> 00:48:44,880
Padeda mums platinti apkrovą visoje
Darbo laikas geriau todėl, kad

1114
00:48:44,880 --> 00:48:45,740
Tai tarsi laimi.

1115
00:48:45,740 --> 00:48:48,860
>> Deja, manau, kad mano instrukcijas
nebuvo iki šiol labai aiškiai, todėl

1116
00:48:48,860 --> 00:48:52,230
Grįžau šį savaitgalį, ir atnaujinamas
didesnėje, drąsiau tekstu spec

1117
00:48:52,230 --> 00:48:53,600
paaiškinti, kulkos, kaip šie.

1118
00:48:53,600 --> 00:48:56,900
Ir tik pasakyti, kad tai daugiau viešai, pagal
Numatytieji, problemų rinkiniai dėl ketvirtadienis

1119
00:48:56,900 --> 00:48:58,400
vidurdienį, už mokymo programas.

1120
00:48:58,400 --> 00:49:02,030
Jei pradėsite anksti, apdailos dalis
problema nustatyti iki trečiadienio 12:00

1121
00:49:02,030 --> 00:49:05,170
PM dalį, kuri susijusi su kuponu
kodas, idėja yra, kad jūs galite išplėsti

1122
00:49:05,170 --> 00:49:07,710
Jūsų terminas
P, nustatytos iki penktadienio.

1123
00:49:07,710 --> 00:49:10,890
Tai reiškia, kad nukando maža dalis P
nustatyti, palyginti su tai, kas paprastai yra

1124
00:49:10,890 --> 00:49:13,200
didesne problema, ir jums pirkti
sau papildomą dieną.

1125
00:49:13,200 --> 00:49:15,190
Vėlgi, tai bus jums galvoti apie
problema rinkinys, paleidžiama jums į

1126
00:49:15,190 --> 00:49:16,380
darbo valandomis anksčiau.

1127
00:49:16,380 --> 00:49:20,670
Bet kuponas problema vis dar
reikia, net jei jūs neturite pateikti jį.

1128
00:49:20,670 --> 00:49:23,340
>> Bet dar priverstinai tai.

1129
00:49:23,340 --> 00:49:26,520
(ETAPAS "WHISPER) Ir tie žmonės palieka
pradžioje yra gonna gailėtis.

1130
00:49:26,520 --> 00:49:28,620
Kaip ir ant balkono žmonės.

1131
00:49:28,620 --> 00:49:32,510
Atsiprašau iš anksto į žmonių su
dėl priežasčių, kurios bus balkonas

1132
00:49:32,510 --> 00:49:33,920
aišku, vos akimirką.

1133
00:49:33,920 --> 00:49:37,050
>> Taigi, mums pasisekė, kad vienas iš
CS50 buvęs galvos mokymo bičiulių ne

1134
00:49:37,050 --> 00:49:39,302
įmonė vadinama dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Jie labai dosniai paaukojo
kuponas čia tai daug vietos,

1136
00:49:45,500 --> 00:49:48,180
kuri yra sudaryti iš
Įprasti 2 GB.

1137
00:49:48,180 --> 00:49:51,740
Taigi, ką aš maniau, mes galėtų padaryti apie tai
Paskutinė pastaba yra padaryti iš dovanų tiek,

1138
00:49:51,740 --> 00:49:55,380
, pagal kurį tik akimirką, mes atskleisti
nugalėtojas, o kas kuponą

1139
00:49:55,380 --> 00:49:57,980
kodas, tada galite eiti į savo
Interneto svetainę, įveskite jį, ir voila, gauti

1140
00:49:57,980 --> 00:50:01,370
daug daugiau ZMI vietos jūsų
prietaisas ir savo asmeninius failus.

1141
00:50:01,370 --> 00:50:05,690
>> Ir pirmasis, kurie norėtų dalyvauti
Šiame piešinyje?

1142
00:50:05,690 --> 00:50:09,630
Gerai, kad dabar tampa dar smagiau.

1143
00:50:09,630 --> 00:50:14,010
Asmuo, kuris gauna šį 25 gigabaitų
kuponas - kuris yra daug

1144
00:50:14,010 --> 00:50:16,150
patrauklesni nei vėlai
dienų dabar, galbūt -

1145
00:50:16,150 --> 00:50:20,620
yra tas, kuris sėdi ant
sėdynės pagalvėlės, žemiau kurios yra

1146
00:50:20,620 --> 00:50:21,620
kad kuponas.

1147
00:50:21,620 --> 00:50:23,480
Dabar galite žiūrėti po
jūsų sėdynės pagalvėlės.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO PLAYBACK]

1150
00:50:29,680 --> 00:50:31,620
>> -Vienas, du, trys.

1151
00:50:31,620 --> 00:50:35,015
>> [Rėkia]

1152
00:50:35,015 --> 00:50:35,985
>> -Jūs gaunate automobilį!

1153
00:50:35,985 --> 00:50:36,670
Jūs gaunate automobilį!

1154
00:50:36,670 --> 00:50:37,970
>> Davidas Malan: Pamatysime
Jūs trečiadienį.

1155
00:50:37,970 --> 00:50:38,904
>> -Jūs gaunate automobilį!

1156
00:50:38,904 --> 00:50:39,371
Jūs gaunate automobilį!

1157
00:50:39,371 --> 00:50:40,305
Jūs gaunate automobilį!

1158
00:50:40,305 --> 00:50:41,706
Jūs gaunate automobilį!

1159
00:50:41,706 --> 00:50:43,107
Jūs gaunate automobilį!

1160
00:50:43,107 --> 00:50:45,530
>> Davidas Malan: Balkonas žmonės, ateik
žemyn čia į priekį,

1161
00:50:45,530 --> 00:50:46,866
kur mes turime priedai.

1162
00:50:46,866 --> 00:50:50,282
>> -Kiekvienas gauna automobilį!

1163
00:50:50,282 --> 00:50:52,234
Kiekvienas gauna automobilį!

1164
00:50:52,234 --> 00:50:52,722
>> [PABAIGA VIDEO PLAYBACK]

1165
00:50:52,722 --> 00:50:54,590
>> Narrator: Kitame CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> GARSIAKALBIS 5: Oh my GOSH Gosh Gosh Gosh
Gosh Gosh Gosh Gosh Gosh Gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukelele vaidina]