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

2
00:00:00,488 --> 00:00:10,800
>> [Musiikki soi]

3
00:00:10,800 --> 00:00:13,500
DAVID MALAN: Okei.

4
00:00:13,500 --> 00:00:14,670
Okei, tervetuloa takaisin.

5
00:00:14,670 --> 00:00:18,120
Joten tämä on viikolla 4, alussa
sen jo.

6
00:00:18,120 --> 00:00:21,320
Ja voit muistaa, että viime viikolla, laitamme
koodata varattu vain vähän

7
00:00:21,320 --> 00:00:24,240
ja aloimme puhua hieman
korkean tason, asioita, kuten

8
00:00:24,240 --> 00:00:28,130
etsiminen ja lajittelu, joka tosin
hieman yksinkertaisia ​​ideoita, ovat

9
00:00:28,130 --> 00:00:31,840
tyypillinen luokan ongelmia
alatte ratkaista erityisesti

10
00:00:31,840 --> 00:00:34,820
kun alkaa miettiä lopullinen
hankkeisiin ja mielenkiintoisia ratkaisuja sinulle

11
00:00:34,820 --> 00:00:36,760
ehkä reaalimaailman ongelmia.

12
00:00:36,760 --> 00:00:39,490
Nyt kupla tavallaan oli yksi yksinkertaisin
tällaisia ​​algoritmeja, ja se

13
00:00:39,490 --> 00:00:42,900
työskenteli ottaa nämä pienet numerot
luettelon tai matriisin sellainen

14
00:00:42,900 --> 00:00:46,530
kupla tiensä ylös, ja
suuret numerot siirtää alas

15
00:00:46,530 --> 00:00:47,930
loppuun luetteloon.

16
00:00:47,930 --> 00:00:50,650
>> Ja muistuttaa, että voisimme visualisoida
kupla tavallaan hieman

17
00:00:50,650 --> 00:00:52,310
jotain tällaista.

18
00:00:52,310 --> 00:00:53,640
Joten anna minun mennä eteenpäin ja napsauta Käynnistä.

19
00:00:53,640 --> 00:00:55,350
Olen ennalta kupla tavallaan.

20
00:00:55,350 --> 00:00:58,920
Ja jos muistatte, että pitempi sininen
linjat edustavat suuret numerot, pieni

21
00:00:58,920 --> 00:01:03,300
siniset viivat edustavat pienien kuin
käymme läpi tämän uudestaan ​​ja uudestaan ​​ja

22
00:01:03,300 --> 00:01:07,680
uudelleen, vertaamalla kaksi baaria vierekkäin
toinen punainen, aiomme vaihtaa

23
00:01:07,680 --> 00:01:11,010
suurin ja pienin, jos
ne ovat epäkunnossa.

24
00:01:11,010 --> 00:01:14,150
>> Joten tämä menee päälle ja mennä ja mennä
on, ja näet, että suurempi

25
00:01:14,150 --> 00:01:16,700
elementit tiensä
oikealle, ja pienemmät elementit ovat

26
00:01:16,700 --> 00:01:17,900
tiensä vasemmalle.

27
00:01:17,900 --> 00:01:21,380
Mutta aloimme määrällisesti
tehokkuutta,

28
00:01:21,380 --> 00:01:22,970
laatu tämä algoritmi.

29
00:01:22,970 --> 00:01:25,200
Ja sanoimme, että pahimmassa
tapauksessa tämä algoritmi kesti

30
00:01:25,200 --> 00:01:27,940
suunnilleen kuinka monta askelta?

31
00:01:27,940 --> 00:01:28,980
>> Joten n potenssiin.

32
00:01:28,980 --> 00:01:30,402
Ja mikä oli n?

33
00:01:30,402 --> 00:01:31,650
>> Yleisö: elementtien määrä.

34
00:01:31,650 --> 00:01:32,790
>> DAVID MALAN: Joten n oli
useita tekijöitä.

35
00:01:32,790 --> 00:01:33,730
Ja niin me teemme tätä usein.

36
00:01:33,730 --> 00:01:36,650
Aina me haluamme puhua koko
ongelma tai kokoa

37
00:01:36,650 --> 00:01:39,140
tulo tai aikaa kuluu
tuottaa tuotos, me vain

38
00:01:39,140 --> 00:01:41,610
yleistynyt riippumatta
tulo on kuin n.

39
00:01:41,610 --> 00:01:45,970
Joten takaisin viikolla 0, numero sivujen
puhelinluettelosta, oli n.

40
00:01:45,970 --> 00:01:47,550
Opiskelijoiden määrä
huone oli n.

41
00:01:47,550 --> 00:01:49,630
Niin täälläkin, olemme jälkeen
että kuvio.

42
00:01:49,630 --> 00:01:52,800
>> Nyt n potenssiin ei ole erityisen
nopeasti, joten yritimme tehdä paremmin.

43
00:01:52,800 --> 00:01:55,970
Ja niin me katsoimme pari
muita algoritmeja, joista

44
00:01:55,970 --> 00:01:57,690
oli valinta lajitella.

45
00:01:57,690 --> 00:01:59,180
Joten valinta tavallaan oli
hieman erilainen.

46
00:01:59,180 --> 00:02:03,130
Se oli melkein yksinkertaisempaa, uskallan sanoa,
jolloin aloitin alussa

47
00:02:03,130 --> 00:02:06,740
luettelo meidän vapaaehtoisille ja minä vain kerran
ja uudestaan ​​ja uudestaan ​​meni läpi

48
00:02:06,740 --> 00:02:10,060
lista, nyppiminen pois pienin
elementti kerrallaan ja työnsivät tai

49
00:02:10,060 --> 00:02:13,040
hänen alussa luettelosta.

50
00:02:13,040 --> 00:02:16,410
>> Mutta tämäkin, kun aloimme ajatella
läpi matematiikka ja isompi

51
00:02:16,410 --> 00:02:19,860
kuva, ajatellut kuinka monta kertaa
Olin menossa edestakaisin ja takaisin

52
00:02:19,860 --> 00:02:24,090
edestakaisin, totesimme pahimmassa tapauksessa
valinta lajitella, liian, oli mitä?

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

54
00:02:24,960 --> 00:02:27,490
Nyt todellisessa maailmassa, se saattaa
todella vähän nopeammin.

55
00:02:27,490 --> 00:02:30,620
Koska taas, en tarvitse pitää
vetäytymistä kerran olin lajiteltu

56
00:02:30,620 --> 00:02:31,880
pienin elementtejä.

57
00:02:31,880 --> 00:02:35,090
Mutta jos ajattelemme hyvin suuri n ja
jos tavallaan tehdä pois matematiikasta sen

58
00:02:35,090 --> 00:02:39,170
Tein pöydällä, jossa n potenssiin
miinus jotain, kaikki muu

59
00:02:39,170 --> 00:02:41,850
lisäksi n potenssiin, kun n
saa todella suuri, ei

60
00:02:41,850 --> 00:02:42,850
oikeastaan ​​väliä niin paljon.

61
00:02:42,850 --> 00:02:45,470
Niin tietotekniikan tutkijoita, me tavallaan
ummistaa silmänsä pienempi

62
00:02:45,470 --> 00:02:49,220
tekijät ja keskittyä vain tekijä
lauseke, joka tulee tehdä

63
00:02:49,220 --> 00:02:50,330
Suurin ero.

64
00:02:50,330 --> 00:02:52,840
>> No, lopuksi, me katsoimme
klo lisäyslajittelu.

65
00:02:52,840 --> 00:02:56,620
Ja tämä oli hengeltään samanlainen, mutta
eikä mene läpi iteratiivisesti ja

66
00:02:56,620 --> 00:03:01,250
Valitse pienin elementti yksitellen
aikaa, olen sen sijaan otti käsi I

67
00:03:01,250 --> 00:03:04,070
oli käsitelty, ja päätin, kaikki
oikeassa, sinä kuulut tänne.

68
00:03:04,070 --> 00:03:06,160
Sitten minä siirryin seuraavaan elementtiin
ja päätti, että hän tai

69
00:03:06,160 --> 00:03:07,470
hän kuului täällä.

70
00:03:07,470 --> 00:03:08,810
Ja sitten muutin ja.

71
00:03:08,810 --> 00:03:11,780
Ja voisin sen, matkan varrella,
siirtää nämä kaverit, jotta

72
00:03:11,780 --> 00:03:13,030
tehdä tilaa heille.

73
00:03:13,030 --> 00:03:16,880
Niin, että oli tavallaan henkistä kääntyminen
valinnan sellaista, että me

74
00:03:16,880 --> 00:03:18,630
nimeltään lisäyslajittelu.

75
00:03:18,630 --> 00:03:20,810
>> Joten näitä aiheita esiintyy
todellisessa maailmassa.

76
00:03:20,810 --> 00:03:23,640
Vain muutama vuosi sitten, kun tietty
senaattori käynnissä presidentiksi,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, tuolloin toimitusjohtaja
Google, todella oli mahdollisuus

78
00:03:27,160 --> 00:03:28,040
haastattelemaan häntä.

79
00:03:28,040 --> 00:03:32,010
Ja ajattelimme jakaa tämän YouTube
clip sinua täällä, jos voisimme kääntää ylös

80
00:03:32,010 --> 00:03:32,950
äänenvoimakkuutta.

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

82
00:03:39,360 --> 00:03:44,620
>> -Senaattori, olet täällä Google,
ja haluan ajatella puheenjohtajakauden

83
00:03:44,620 --> 00:03:46,042
kuin työhaastattelu.

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

85
00:03:47,770 --> 00:03:50,800
>> -Nyt on vaikea saada
työtä presidenttinä.

86
00:03:50,800 --> 00:03:52,480
Ja olet menossa läpi
jäykkyys nyt.

87
00:03:52,480 --> 00:03:54,330
On myös vaikea saada työpaikan Google.

88
00:03:54,330 --> 00:03:59,610
Meillä on kysymyksiä ja pyydämme
meidän ehdokkaita kysymyksiä.

89
00:03:59,610 --> 00:04:02,250
Ja tämä yksi on Larry Schwimmer.

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

91
00:04:05,325 --> 00:04:06,400
-Luuletteko olen tosissasi?

92
00:04:06,400 --> 00:04:08,750
Se on täällä.

93
00:04:08,750 --> 00:04:12,110
Mikä on tehokkain tapa
lajitella miljoonaa kahden bitin kokonaislukuja?

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

95
00:04:15,810 --> 00:04:18,260
>> -No, öh -

96
00:04:18,260 --> 00:04:19,029
>> -Olen pahoillani.

97
00:04:19,029 --> 00:04:19,745
Ehkä meidän pitäisi -

98
00:04:19,745 --> 00:04:21,000
>> -Ei, ei, ei, ei, ei.

99
00:04:21,000 --> 00:04:21,470
>> -Se ei ole -

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

101
00:04:22,185 --> 00:04:25,328
>> -Mielestäni kupla semmoista
on väärä tapa edetä.

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

103
00:04:26,792 --> 00:04:28,510
>> [Hurraavat ja suosionosoituksia]

104
00:04:28,510 --> 00:04:31,211
>> -Tule, jotka kertoivat hänelle tämän?

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

106
00:04:32,155 --> 00:04:33,350
>> [END VIDEOTOISTOSTA]

107
00:04:33,350 --> 00:04:35,070
>> DAVID MALAN: Siinäpä se.

108
00:04:35,070 --> 00:04:39,600
Joten aloimme määrällisesti näiden käynnissä
kertaa, niin sanotusti, jotain

109
00:04:39,600 --> 00:04:43,480
kutsutaan asymptoottinen merkintätapa, joka on
tarkoita pelkästään meidän eräänlainen käännekohta

110
00:04:43,480 --> 00:04:47,420
silmänsä ne pienet tekijät ja
tarkastellaan vain ajoaika

111
00:04:47,420 --> 00:04:51,250
suorituskykyä näiden algoritmien
N saa todella suuren ajan.

112
00:04:51,250 --> 00:04:55,110
Ja niin me otettiin iso O. Ja iso O
edustaa jotain, ajattelimme

113
00:04:55,110 --> 00:04:57,000
AS ylärajana.

114
00:04:57,000 --> 00:04:59,570
Ja todella, Barry, voimme laskea
kuin mic vähän?

115
00:04:59,570 --> 00:05:01,040
>> Ajattelimme tämän on yläraja.

116
00:05:01,040 --> 00:05:04,710
Joten iso O n potenssiin tarkoittaa, että
Pahimmassa tapauksessa jotain

117
00:05:04,710 --> 00:05:07,780
valinta sort veisi
n potenssiin vaiheet.

118
00:05:07,780 --> 00:05:10,310
Tai jotain lisäyslajittelu
olisi n potenssiin vaiheet.

119
00:05:10,310 --> 00:05:15,150
Nyt jotain paikoilleen
lajitella, mikä oli pahin?

120
00:05:15,150 --> 00:05:18,200
Koska joukko, mikä on pahin
mahdollinen skenaario, että saatat löytää

121
00:05:18,200 --> 00:05:20,650
itsesi edessä?

122
00:05:20,650 --> 00:05:21,860
>> Se on täysin taaksepäin, eikö?

123
00:05:21,860 --> 00:05:24,530
Koska jos se on täysin taaksepäin,
sinun täytyy tehdä paljon työtä.

124
00:05:24,530 --> 00:05:26,420
Koska jos olet täysin taaksepäin,
olet menossa löytää

125
00:05:26,420 --> 00:05:28,840
Suurin osa täällä, vaikka
se kuuluu sinne.

126
00:05:28,840 --> 00:05:31,140
Joten aiot sanoa, okei, kello
tällä hetkellä, et kuulu tänne,

127
00:05:31,140 --> 00:05:32,310
niin jätät sen yksin.

128
00:05:32,310 --> 00:05:35,425
>> Niin huomaat, oh, damn, minun on
siirtää tätä hieman pienempi tekijä

129
00:05:35,425 --> 00:05:36,470
vasemmalla teistä.

130
00:05:36,470 --> 00:05:38,770
Sitten minun täytyy tehdä se uudestaan
ja uudestaan ​​ja uudestaan.

131
00:05:38,770 --> 00:05:41,410
Ja jos minä kävelin edestakaisin, sinä
olisi tavallaan tuntuu suorituskykyä

132
00:05:41,410 --> 00:05:45,540
että algoritmi, koska jatkuvasti olen
laahustavat kaikki muutkin alas

133
00:05:45,540 --> 00:05:46,510
array tehdä sille tilaa.

134
00:05:46,510 --> 00:05:47,750
Niin, että pahimmassa tapauksessa.

135
00:05:47,750 --> 00:05:48,570
>> Sen sijaan -

136
00:05:48,570 --> 00:05:50,320
ja tämä oli jännitysnäytelmä viimeisen kerran -

137
00:05:50,320 --> 00:05:54,065
sanoimme, että lisäyslajittelu
oli omega, mitä?

138
00:05:54,065 --> 00:05:57,530
Mikä on parhaassa tapauksessa käynnissä
aika lisäyslajittelu?

139
00:05:57,530 --> 00:05:58,520
Joten se on todella n.

140
00:05:58,520 --> 00:06:00,980
Se oli tyhjä, että lähdimme
taululle viimeisen kerran.

141
00:06:00,980 --> 00:06:03,160
>> Ja se on omega n koska miksi?

142
00:06:03,160 --> 00:06:06,630
No, parasta tapauksessa mitä
lisäyslajittelu aiotaan luovuttaa?

143
00:06:06,630 --> 00:06:09,830
No, luettelo, joka on täysin lajiteltu
jo vähän työtä tehdä.

144
00:06:09,830 --> 00:06:12,460
Mutta mitä on siisti noin lisäyslajittelu
on, että koska se alkaa täällä

145
00:06:12,460 --> 00:06:15,340
päättää, oh, olet numero
yksi, sinä kuulut tänne.

146
00:06:15,340 --> 00:06:16,970
Voi, mikä onni.

147
00:06:16,970 --> 00:06:17,740
>> Olet numero kaksi.

148
00:06:17,740 --> 00:06:19,030
Sinulla on myös kuulu tänne.

149
00:06:19,030 --> 00:06:21,010
Numero kolme, jopa parempi,
et kuulu tänne.

150
00:06:21,010 --> 00:06:25,210
Heti kun se saa loppuun
lista, per lisäyslajittelu n pseudokoodina

151
00:06:25,210 --> 00:06:28,010
että kävelimme läpi suullisesti
Viimeisen kerran, se on tehty.

152
00:06:28,010 --> 00:06:32,790
Mutta valinta lajitella, sen sijaan,
pidetään tekee mitä?

153
00:06:32,790 --> 00:06:35,260
>> Piti läpi lista
uudestaan ​​ja uudestaan ​​ja uudestaan.

154
00:06:35,260 --> 00:06:39,160
Koska keskeinen oivallus oli vain
kun olet etsinyt aina

155
00:06:39,160 --> 00:06:42,500
luettelon loppuun voit olla varma
että elementti valitsemasi oli

156
00:06:42,500 --> 00:06:45,560
todellakin tällä hetkellä pienin elementti.

157
00:06:45,560 --> 00:06:48,920
Niinpä nämä eri ajattelumallien lopussa
up saatiin hyvin reaalimaailman

158
00:06:48,920 --> 00:06:53,130
eroja meille, sekä näiden
teoreettinen asymptoottinen eroja.

159
00:06:53,130 --> 00:06:56,910
>> Joten vain kertaus, sitten iso O n
potenssiin, olemme nähneet muutamia tällaisia

160
00:06:56,910 --> 00:06:58,350
algoritmeja toistaiseksi.

161
00:06:58,350 --> 00:06:59,580
Big O n?

162
00:06:59,580 --> 00:07:02,870
Mitä algoritmi, joka voisi
sanoa olevan iso O n?

163
00:07:02,870 --> 00:07:06,930
Pahimmassa tapauksessa, se kestää
lineaarinen useita vaiheita.

164
00:07:06,930 --> 00:07:07,810
>> OK, lineaarista hakua.

165
00:07:07,810 --> 00:07:10,470
Ja pahimmassa tapauksessa, jossa on
elementti etsit, kun

166
00:07:10,470 --> 00:07:12,950
soveltamalla lineaarista hakua?

167
00:07:12,950 --> 00:07:14,680
>> OK, pahimmassa tapauksessa,
se ei ole edes olemassa.

168
00:07:14,680 --> 00:07:17,000
Tai toiseen pahimmassa tapauksessa se on
aina lopulta, joka on

169
00:07:17,000 --> 00:07:18,880
plus-tai miinus-yksi-vaihe ero.

170
00:07:18,880 --> 00:07:21,180
Joten lopussa päivä,
Voimme sanoa, että se lineaarinen.

171
00:07:21,180 --> 00:07:23,910
Big O n olisi lineaarinen haku,
sillä pahimmassa tapauksessa,

172
00:07:23,910 --> 00:07:26,610
elementti ei ole edes olemassa tai se on
koko matkan lopussa.

173
00:07:26,610 --> 00:07:29,370
>> No, iso O log n.

174
00:07:29,370 --> 00:07:32,760
Emme puhuneet hyvin yksityiskohtaisesti noin
, mutta olemme nähneet tämän ennenkin.

175
00:07:32,760 --> 00:07:36,840
Mikä toimii ns logaritminen
aikaa, pahimmassa tapauksessa?

176
00:07:36,840 --> 00:07:38,500
>> Joo, niin binäärihaku.

177
00:07:38,500 --> 00:07:42,930
Ja binäärihaku pahimmassa tapauksessa
saattaa olla tekijä jossain

178
00:07:42,930 --> 00:07:45,640
keski-tai jonnekin
sisällä array.

179
00:07:45,640 --> 00:07:48,040
Mutta et vain löydä sitä kerran
jakaa listan kahtia, vuonna

180
00:07:48,040 --> 00:07:48,940
puoli, puoli, puoli.

181
00:07:48,940 --> 00:07:50,200
Ja sitten voila, se on olemassa.

182
00:07:50,200 --> 00:07:52,500
Tai jälleen, pahimmassa tapauksessa
se ei ole edes olemassa.

183
00:07:52,500 --> 00:07:56,770
Mutta et tiedä, että se ei ole siellä
kunnes tavallaan päästä, että viime

184
00:07:56,770 --> 00:08:00,470
alimmaisen elementtejä puolittamalla
ja puolittaa ja puolittaa.

185
00:08:00,470 --> 00:08:01,400
>> Big O 1.

186
00:08:01,400 --> 00:08:03,540
Joten voisimme iso O 2, iso O 3.

187
00:08:03,540 --> 00:08:06,260
Milloin haluat vain vakiomäärä,
me vain eräänlainen vain yksinkertaistaa

188
00:08:06,260 --> 00:08:07,280
että iso O 1.

189
00:08:07,280 --> 00:08:10,440
Vaikka jos realistisesti, se kestää
2 tai jopa 100 askeleen, jos se on

190
00:08:10,440 --> 00:08:13,680
jatkuvasti useita vaiheita,
me vain sanoa iso O 1.

191
00:08:13,680 --> 00:08:15,930
Mitä algoritmi, joka on
iso O 1?

192
00:08:15,930 --> 00:08:18,350
>> Yleisö: Finding pituus
muuttujan.

193
00:08:18,350 --> 00:08:21,090
>> DAVID MALAN: Finding
pituus muuttuvan?

194
00:08:21,090 --> 00:08:23,870
>> Yleisö: Ei, pituus
jos se on jo järjestetty.

195
00:08:23,870 --> 00:08:24,160
>> DAVID MALAN: Hyvä.

196
00:08:24,160 --> 00:08:27,850
OK, niin löytää pituus jotain
jos pituus, että jotain, kuten

197
00:08:27,850 --> 00:08:30,020
array, tallennetaan joissakin muuttuja.

198
00:08:30,020 --> 00:08:33,380
Koska voit lukea muuttujan
tai tulostaa muuttujan tai

199
00:08:33,380 --> 00:08:34,960
vain yleisesti käyttää muuttuja.

200
00:08:34,960 --> 00:08:37,299
Ja voila, että kestää jatkuvaa aikaa.

201
00:08:37,299 --> 00:08:38,909
>> Sen sijaan muistelen raapia.

202
00:08:38,909 --> 00:08:42,460
Muistelen ensimmäisellä viikolla C,
soittaa vain printf ja tulostus

203
00:08:42,460 --> 00:08:46,240
jotain ruudulla on kiistatta
vakioaikaisia, koska se vain vie

204
00:08:46,240 --> 00:08:50,880
joitakin määrä suorittimen käytön näyttää
että tekstiä ruudulla.

205
00:08:50,880 --> 00:08:52,720
Tai odota - eihän?

206
00:08:52,720 --> 00:08:56,430
Miten muuten voisimme mallintaa
suorituskykyä printf?

207
00:08:56,430 --> 00:09:00,420
Voisiko joku olla eri mieltä, että
ehkä se ei ole oikeastaan ​​jatkuvaa aikaa?

208
00:09:00,420 --> 00:09:03,600
Missä mielessä voisi printf juoksee
aikaa, oikeastaan ​​tulostaa merkkijonon

209
00:09:03,600 --> 00:09:05,580
näyttö, olla jotain
muuta kuin vakio.

210
00:09:05,580 --> 00:09:07,860
>> Yleisö: [kuultavissa].

211
00:09:07,860 --> 00:09:08,230
>> DAVID MALAN: Joo.

212
00:09:08,230 --> 00:09:09,300
Joten se riippuu meidän näkökulmasta.

213
00:09:09,300 --> 00:09:13,390
Jos me todella ajattelemme panos
printf olevan merkkijonon, ja

214
00:09:13,390 --> 00:09:16,380
Siksi me mittaamme koko kyseisen
syöttää sen pituus - joten kutsukaamme

215
00:09:16,380 --> 00:09:17,780
että pituus n sekä -

216
00:09:17,780 --> 00:09:21,990
Ilmeisesti printf on itse iso O n
koska se vie sinut n toimet

217
00:09:21,990 --> 00:09:24,750
tulostaa kaikki nämä n
merkkiä, todennäköisesti.

218
00:09:24,750 --> 00:09:27,730
Ainakin siltä osin, että oletamme
että ehkä se käyttää silmukka

219
00:09:27,730 --> 00:09:28,560
alla huppu.

220
00:09:28,560 --> 00:09:30,860
>> Mutta meidän olisi tarkasteltava, että
Koodi ymmärtää sitä paremmin.

221
00:09:30,860 --> 00:09:33,650
Ja todellakin, kun kaverit alkaa
analysoida omia algoritmeja, sinun

222
00:09:33,650 --> 00:09:34,900
kirjaimellisesti tehdä juuri niin.

223
00:09:34,900 --> 00:09:37,765
Lajittele silmämunan koodi ja ajatella
noin - kaikki hyvin, minulla on tämä silmukka

224
00:09:37,765 --> 00:09:41,870
tässä tai minulla on sisäkkäisiä silmukoita täällä,
että aikoo tehdä n asioita n kertaa,

225
00:09:41,870 --> 00:09:46,050
ja voit lajitella järjen tiesi
koodin läpi, vaikka se on

226
00:09:46,050 --> 00:09:47,980
pseudokoodina eikä varsinainen koodi.

227
00:09:47,980 --> 00:09:49,730
>> Entä omega n potenssiin?

228
00:09:49,730 --> 00:09:53,582
Mikä on algoritmi, joka on paras
tapauksessa edelleen otti n potenssiin vaiheet?

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

230
00:09:54,014 --> 00:09:54,880
>> Yleisö: [kuultavissa].

231
00:09:54,880 --> 00:09:55,900
>> DAVID MALAN: Joten valinta lajitella.

232
00:09:55,900 --> 00:09:59,150
Koska tämä ongelma todella vähentää
siihen, että jälleen, en tiedä

233
00:09:59,150 --> 00:10:02,600
Olen löytänyt nykyisen pienin asti
Olen tarkistanut kaikki hiton elementtejä.

234
00:10:02,600 --> 00:10:08,050
Joten omega vaikkapa n, me
tuli juuri yksi.

235
00:10:08,050 --> 00:10:09,300
Lisäyslajittelu.

236
00:10:09,300 --> 00:10:12,370
Jos luettelo sattuu lajitella
jo, parhaassa tapauksessa meidän on vain

237
00:10:12,370 --> 00:10:15,090
tehdä kerralla läpi,
jolloin emme varmasti.

238
00:10:15,090 --> 00:10:17,890
Ja sitten, että voidaan sanoa
olla lineaarinen, varmasti.

239
00:10:17,890 --> 00:10:20,570
>> Entä omega 1?

240
00:10:20,570 --> 00:10:23,790
Mitä, parhaassa tapauksessa saattaa kestää
jatkuva useita vaiheita?

241
00:10:23,790 --> 00:10:27,220
Joten lineaarinen haku, jos vain onnekas
ja elementin etsit

242
00:10:27,220 --> 00:10:31,000
on aivan listan alkuun,
jos se jos olet aloittamassa

243
00:10:31,000 --> 00:10:33,070
lineaarinen läpikäyminen luetteloon.

244
00:10:33,070 --> 00:10:35,180
>> Ja tämä on totta
useita asioita.

245
00:10:35,180 --> 00:10:37,660
Esimerkiksi jopa binary
haku on omega 1.

246
00:10:37,660 --> 00:10:40,310
Koska mitä jos saat todella hiton
onnekas ja ihan keskellä

247
00:10:40,310 --> 00:10:42,950
levyjärjestelmän on määrä
etsit?

248
00:10:42,950 --> 00:10:45,730
Joten voit saada onnekas siellä samoin.

249
00:10:45,730 --> 00:10:49,190
>> Tämä yksi, lopuksi omega n log n.

250
00:10:49,190 --> 00:10:52,573
Joten n log n, emme oikeastaan
puhua vielä, mutta -

251
00:10:52,573 --> 00:10:53,300
>> Yleisö: Merge sort?

252
00:10:53,300 --> 00:10:53,960
>> DAVID MALAN: Merge sort.

253
00:10:53,960 --> 00:10:56,920
Se oli jännitysnäytelmä viime aikaa,
jossa ehdotimme, ja osoitimme

254
00:10:56,920 --> 00:10:58,600
visuaalisesti, että on olemassa algoritmeja.

255
00:10:58,600 --> 00:11:02,470
Ja yhdistää tavallaan vain yksi tällainen
algoritmi, joka on pohjimmiltaan nopeampi

256
00:11:02,470 --> 00:11:03,450
kuin jotkut näistä muista tyyppejä.

257
00:11:03,450 --> 00:11:07,800
Itse asiassa, yhdistää lyhyt ei ainoastaan
Parhaassa tapauksessa n log n, pahimmassa

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

259
00:11:09,460 --> 00:11:14,540
Ja kun sinulla on tämä sattuma
omega ja iso O on sama asia?

260
00:11:14,540 --> 00:11:17,310
Voimme itse kuvata, että mitä
kutsutaan theta, vaikka se on

261
00:11:17,310 --> 00:11:18,220
hieman harvinaisempia.

262
00:11:18,220 --> 00:11:21,730
Mutta se tarkoittaa vain kaksi bounds,
tässä tapauksessa ovat samat.

263
00:11:21,730 --> 00:11:25,770
>> Joten yhdistää tavallaan, mitä tämä
todella pohjimmiltaan meille?

264
00:11:25,770 --> 00:11:27,000
No, muistaa motivaatio.

265
00:11:27,000 --> 00:11:30,340
Saanen vetää toinen animaatio
emme katso viimeinen kerta.

266
00:11:30,340 --> 00:11:33,390
Tämä yksi, sama idea, mutta
se on hieman suurempi.

267
00:11:33,390 --> 00:11:36,160
Ja aion mennä eteenpäin ja huomauttaa
Ensimmäinen - meillä on lisäyslajittelu on

268
00:11:36,160 --> 00:11:39,410
vasemmassa yläkulmassa, niin valinta lajitella,
kupla lajitella, pari muunkinlaisia ​​-

269
00:11:39,410 --> 00:11:42,670
kuori ja nopea - että emme ole keskustelleet
noin, ja kasaan ja yhdistää tavallaan.

270
00:11:42,670 --> 00:11:47,090
>> Joten ainakin yrittää keskittyä silmäsi
kärkikolmikkoon vasemmalle ja sitten

271
00:11:47,090 --> 00:11:49,120
yhdistää eräänlainen kun klikkaa
Tämä vihreä nuoli.

272
00:11:49,120 --> 00:11:51,900
Mutta minä annan ne kaikki ajaa, vain
antaa sinulle tunteen monimuotoisuuden

273
00:11:51,900 --> 00:11:53,980
algoritmeja, että olemassa maailmassa.

274
00:11:53,980 --> 00:11:56,180
Aion antaa tämän nousun
vain muutaman sekunnin.

275
00:11:56,180 --> 00:11:59,640
Ja jos keskittyä silmäsi - pick
algoritmi, keskittyä siihen vain

276
00:11:59,640 --> 00:12:02,970
sekuntia - voit alkaa nähdä
kuvio, että se toteuttaa.

277
00:12:02,970 --> 00:12:04,530
>> Yhdistä lajitella, ilmoitus on tehty.

278
00:12:04,530 --> 00:12:06,430
Heap lajitella, nopeasti lajitella, kuori -

279
00:12:06,430 --> 00:12:09,480
joten se näyttää esittelimme kolme
pahin algoritmit viime viikolla.

280
00:12:09,480 --> 00:12:12,960
Mutta se on hyvä, että olemme täällä tänään
katso yhdistäminen lajitella, joka on yksi

281
00:12:12,960 --> 00:12:16,500
helpommalla on tarkastella, vaikka
vaikka se todennäköisesti taipuu mielesi

282
00:12:16,500 --> 00:12:17,490
vain vähän.

283
00:12:17,490 --> 00:12:21,130
Täällä voimme nähdä, kuinka paljon
valinta lajitella perseestä.

284
00:12:21,130 --> 00:12:24,600
>> Mutta kääntöpuoli, se on
todella helppo toteuttaa.

285
00:12:24,600 --> 00:12:28,160
Ja ehkä P Set 3, joka on yksi
algoritmeja valitsit toteuttaa

286
00:12:28,160 --> 00:12:28,960
standardin painos.

287
00:12:28,960 --> 00:12:30,970
Hienosäätää, aivan oikeassa.

288
00:12:30,970 --> 00:12:35,210
>> Mutta jälleen kerran, kun n saa suuret, jos
päättää panna nopeammin algoritmi

289
00:12:35,210 --> 00:12:39,020
kuin sulautua lajitella, kertoimet ovat suurempia ja
Suuremmat tulot, koodi on vain

290
00:12:39,020 --> 00:12:39,800
menossa ajaa nopeammin.

291
00:12:39,800 --> 00:12:41,090
Sivuston tulee toimimaan paremmin.

292
00:12:41,090 --> 00:12:42,650
Käyttäjät tulevat olemaan onnellisempi.

293
00:12:42,650 --> 00:12:45,280
Ja niin on nämä vaikutukset
todella antaa

294
00:12:45,280 --> 00:12:47,350
meille hieman syvemmällä ajatellut.

295
00:12:47,350 --> 00:12:49,990
>> Joten katsomaan mitä sulautua
sort on oikeastaan ​​kyse.

296
00:12:49,990 --> 00:12:52,992
Viileä asia on, että sulautuvat
sort on juuri tämä.

297
00:12:52,992 --> 00:12:56,300
Tämä on taas mitä me olemme kutsuneet
pseudokoodit pseudokoodina olento

298
00:12:56,300 --> 00:12:57,720
Englanti-syntaksi.

299
00:12:57,720 --> 00:12:59,890
Ja yksinkertaisuus on
tavallaan kiehtovaa.

300
00:12:59,890 --> 00:13:02,840
>> Joten tulo n elementtejä - niin, että
tarkoittaa vain sitä, tässä on jono.

301
00:13:02,840 --> 00:13:04,000
Se sai n asioita siinä.

302
00:13:04,000 --> 00:13:05,370
Siinä kaikki sanomme siellä.

303
00:13:05,370 --> 00:13:07,560
>> Jos n on pienempi kuin 2, palaa.

304
00:13:07,560 --> 00:13:08,640
Joten se on vain vähäpätöinen asia.

305
00:13:08,640 --> 00:13:12,580
Jos n on pienempi kuin 2, niin ilmeisesti se on
1 tai 0, jolloin asia

306
00:13:12,580 --> 00:13:14,780
on jo järjestetty tai olematon,
niin vain palata.

307
00:13:14,780 --> 00:13:15,900
Ei mitään tekemistä.

308
00:13:15,900 --> 00:13:18,360
Niin, että yksinkertainen asia nyppiä pois.

309
00:13:18,360 --> 00:13:20,110
>> Else, meillä on kolme vaihetta.

310
00:13:20,110 --> 00:13:23,650
Lajitella vasen puoli elementtejä, lajitella
oikealla puolella elementtejä,

311
00:13:23,650 --> 00:13:26,650
ja sitten yhdistää lajiteltu puolikkaat.

312
00:13:26,650 --> 00:13:29,400
Mielenkiintoista tässä on se, että
Olen sellainen punting, eikö?

313
00:13:29,400 --> 00:13:32,300
On sellainen pyöreä määritelmän
Tämän algoritmin.

314
00:13:32,300 --> 00:13:35,986
Missä mielessä tämä algoritmi
määritelmä pyöreä?

315
00:13:35,986 --> 00:13:37,850
>> Yleisö: [kuultavissa].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Joo, minun lajittelu algoritmi,
kaksi sen vaiheet ovat "tavallaan

317
00:13:41,670 --> 00:13:44,640
jotain. "Ja niin, että herättää
kysymys, hyvin, mitä aion käyttää

318
00:13:44,640 --> 00:13:46,460
lajitella vasen puoli
ja oikea puoli?

319
00:13:46,460 --> 00:13:49,600
Ja kauneus tässä on se, että vaikka
kerran, tämä on aistiharhoja

320
00:13:49,600 --> 00:13:54,030
osa mahdollisesti voit käyttää samaa
algoritmi lajitella vasen puoli.

321
00:13:54,030 --> 00:13:54,700
>> Mutta hetkinen.

322
00:13:54,700 --> 00:13:57,070
Kun olet kertonut lajitella
vasen puoli, mitkä ovat kaksi

323
00:13:57,070 --> 00:13:58,240
vaiheet tulee seuraavaksi?

324
00:13:58,240 --> 00:14:00,550
Me lajitella vasen puoli
vasen puoli ja oikea

325
00:14:00,550 --> 00:14:01,420
puolet vasen puoli.

326
00:14:01,420 --> 00:14:04,430
Hitto, miten voin lajitella nämä kaksi
puolikkaat tai neljännekset, nyt?

327
00:14:04,430 --> 00:14:05,260
>> Mutta se on OK.

328
00:14:05,260 --> 00:14:07,830
Meillä on Lajittelualgoritmi täällä.

329
00:14:07,830 --> 00:14:10,660
Ja vaikka saatat huolehtia ollenkaan
Aluksi tämä on eräänlainen ääretön

330
00:14:10,660 --> 00:14:12,780
silmukka, se on sykli, joka ei ole koskaan
ehdi - se on menossa

331
00:14:12,780 --> 00:14:15,770
päättyy, kun mitä tapahtuu?

332
00:14:15,770 --> 00:14:16,970
Kun n on pienempi kuin 2.

333
00:14:16,970 --> 00:14:19,180
Joka lopulta tulee tapahtumaan,
koska jos pitää puolittaa ja

334
00:14:19,180 --> 00:14:23,020
puolittaa puolittamaan nämä puolikkaat, varmasti
lopulta olet menossa loppuun

335
00:14:23,020 --> 00:14:25,350
jopa vain 1 tai 0 elementtejä.

336
00:14:25,350 --> 00:14:28,500
Jolloin tämä algoritmi
sanoo olet valmis.

337
00:14:28,500 --> 00:14:31,020
>> Joten todellinen taika tässä
algoritmi näyttää olevan

338
00:14:31,020 --> 00:14:33,470
että viimeinen vaihe, yhdistäminen.

339
00:14:33,470 --> 00:14:37,190
Tämä yksinkertainen ajatus vain yhdistämällä kaksi
asioita, se mitä lopulta tapahtuu

340
00:14:37,190 --> 00:14:40,920
jotta voimme järjestää erilaisia,
sanotaanko, kahdeksan elementtejä.

341
00:14:40,920 --> 00:14:44,410
Olen siis kahdeksan enemmän stressiä palloja ylös
täällä kahdeksan paperille, ja yksi

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

343
00:14:45,500 --> 00:14:46,140
jonka saan pitää.

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

345
00:14:46,960 --> 00:14:48,970
>> DAVID MALAN: Jos voisimme ottaa kahdeksan
vapaaehtoisia, ja katsotaan jos voimme

346
00:14:48,970 --> 00:14:51,430
pelata tätä ulos, niin.

347
00:14:51,430 --> 00:14:52,500
Vau, OK.

348
00:14:52,500 --> 00:14:53,565
Tietotekniikassa on tulossa hauskaa.

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

350
00:14:54,320 --> 00:14:57,770
Niin miten te kolme,
Suurin käsi ylös.

351
00:14:57,770 --> 00:14:58,580
Neljä takana.

352
00:14:58,580 --> 00:15:02,220
Ja miten me teemme sinulle
kolme tällä rivillä?

353
00:15:02,220 --> 00:15:03,390
Ja neljä edessä.

354
00:15:03,390 --> 00:15:04,920
Joten te kahdeksan, tule ylös.

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

356
00:15:12,060 --> 00:15:13,450
>> DAVID MALAN: Olen oikeastaan
ole varma, mitä se on.

357
00:15:13,450 --> 00:15:14,810
Onko stressi pallot?

358
00:15:14,810 --> 00:15:16,510
Kirjoituspöydän lamput?

359
00:15:16,510 --> 00:15:18,650
Materiaalia?

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

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

362
00:15:20,160 --> 00:15:21,310
Joten tule ylös.

363
00:15:21,310 --> 00:15:22,310
Kuka haluaisi -

364
00:15:22,310 --> 00:15:23,570
tulee koko ajan.

365
00:15:23,570 --> 00:15:24,240
Katsotaanpa.

366
00:15:24,240 --> 00:15:26,460
Ja tämä asettaa sinut paikkaan -

367
00:15:26,460 --> 00:15:27,940
olet paikalla yksi.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, odota hetki.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - OH, hyvä.

370
00:15:30,760 --> 00:15:31,310
Okei, olemme hyviä.

371
00:15:31,310 --> 00:15:35,130
Okei, joten jokainen on paikka,
mutta ei Google Glass.

372
00:15:35,130 --> 00:15:36,475
Saanen jonottaa nämä ylös.

373
00:15:36,475 --> 00:15:37,115
Mikä sinun nimesi on?

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

375
00:15:37,440 --> 00:15:38,090
>> DAVID MALAN: Michelle?

376
00:15:38,090 --> 00:15:42,000
Okei, saat näyttää
pelle, jos se on OK.

377
00:15:42,000 --> 00:15:44,625
No, minä myös, oletan,
vain hetken.

378
00:15:44,625 --> 00:15:45,875
Okei, valmiustilassa.

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

380
00:15:48,510 --> 00:15:50,950
Olemme yrittäneet keksiä
käyttää tapauksessa Google Glass, ja me

381
00:15:50,950 --> 00:15:53,750
ajattelin että olisi hauskaa vain tehdä
Tässä kun ihmiset ovat lavalla.

382
00:15:53,750 --> 00:15:57,120
Me tallentaa maailman
heidän näkökulmastaan.

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

384
00:15:58,410 --> 00:15:59,830
Ei luultavasti mitä Google tarkoitettu.

385
00:15:59,830 --> 00:16:02,260
Okei, jos et mielessä yllään
Tämän seuraavan hankala minuuttia,

386
00:16:02,260 --> 00:16:03,150
Se olisi hienoa.

387
00:16:03,150 --> 00:16:08,620
>> Okei, joten meillä on täällä joukko
elementtejä, ja että array, kohti

388
00:16:08,620 --> 00:16:11,480
paperinpaloja nämä ihmiset "
kädet, on tällä hetkellä lajittelematta.

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE: Voi, se on niin outoa.

390
00:16:12,050 --> 00:16:12,810
>> DAVID MALAN: Se on aika paljon satunnaisia.

391
00:16:12,810 --> 00:16:15,760
Ja vain hetken, aiomme kokeilla
toteuttaa yhdistää tavallaan yhdessä

392
00:16:15,760 --> 00:16:17,950
ja katso, että keskeiset oivallus on.

393
00:16:17,950 --> 00:16:21,970
Ja temppu täällä merge sort on
jotain, että emme ole oletettu vielä.

394
00:16:21,970 --> 00:16:24,030
Me todella tarvitsemme
lisätilaa.

395
00:16:24,030 --> 00:16:26,650
Joten mitä tulee olemaan erityisen
mielenkiintoista tässä on se, että nämä

396
00:16:26,650 --> 00:16:29,270
kaverit ovat menossa liikkua hieman
vähän, koska aion olettaa, että

397
00:16:29,270 --> 00:16:31,880
siellä on ylimääräistä joukko tilaa,
sanoa, oikealla takana.

398
00:16:31,880 --> 00:16:34,570
>> Joten jos he takana tuoli,
se toissijainen array.

399
00:16:34,570 --> 00:16:36,960
Jos he istuvat täällä, se on
ensisijainen jono.

400
00:16:36,960 --> 00:16:40,170
Mutta tämä on voimavara, että meillä on
ei velkarahalla toistaiseksi kupla

401
00:16:40,170 --> 00:16:42,040
lajitella, jossa valinta lajitella,
kanssa lisäyslajittelu.

402
00:16:42,040 --> 00:16:44,600
Recall viime viikolla, kaikki vain
Tällainen sekoitetaan paikallaan.

403
00:16:44,600 --> 00:16:46,840
He eivät käytä mitään lisämuistia.

404
00:16:46,840 --> 00:16:49,310
Teimme tilaa ihmisten
liikkuvat ihmiset ympärillä.

405
00:16:49,310 --> 00:16:50,580
>> Joten tämä on keskeinen oivallus, too.

406
00:16:50,580 --> 00:16:53,410
Ei tämä kompromissi, yleisesti
tietojenkäsittelytiede, resursseja.

407
00:16:53,410 --> 00:16:55,800
Jos haluat nopeuttaa jotain
kuten aika, olet menossa

408
00:16:55,800 --> 00:16:56,900
on maksettava hinta.

409
00:16:56,900 --> 00:17:00,750
Ja yksi näistä hinnoista on hyvin usein
tilaa, muistin määrän tai kova

410
00:17:00,750 --> 00:17:01,700
levytilaa, että käytät.

411
00:17:01,700 --> 00:17:03,640
Tai suoraan sanoen määrä
ohjelmoija aikaa.

412
00:17:03,640 --> 00:17:06,700
Kuinka paljon aikaa se vie, ihmisten,
todella toteuttaa joitakin enemmän

413
00:17:06,700 --> 00:17:07,829
monimutkainen algoritmi.

414
00:17:07,829 --> 00:17:09,760
Mutta tänään, kauppa-off
on aikaa ja tilaa.

415
00:17:09,760 --> 00:17:11,930
>> Joten jos te voisi vain pitäkää
numerot, jotta voimme nähdä, että olet

416
00:17:11,930 --> 00:17:15,839
todellakin vastaa 4, 2, 6, 1, 3, 7, 8.

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

418
00:17:16,599 --> 00:17:19,520
Joten aion yrittää johdatella
asioita, jos te voitte vain

419
00:17:19,520 --> 00:17:21,800
noudattaa esimerkkiäni täällä.

420
00:17:21,800 --> 00:17:26,650
>> Joten aion toteuttaa, ensin,
ensimmäisessä vaiheessa pseudokoodi, joka on

421
00:17:26,650 --> 00:17:29,440
syötettyjen n osia, jos n on
alle 2, palaa sitten.

422
00:17:29,440 --> 00:17:31,370
On selvää, että ei
apply, joten siirrymme.

423
00:17:31,370 --> 00:17:33,340
Joten lajitella vasemmalla puolella elementtejä.

424
00:17:33,340 --> 00:17:36,220
Niin se tarkoittaa, aion keskittyä minun
huomiota vain hetken seuraavilla

425
00:17:36,220 --> 00:17:37,310
neljä kaveria täällä.

426
00:17:37,310 --> 00:17:39,774
Okei, mitä teen seuraavaksi tehdä?

427
00:17:39,774 --> 00:17:40,570
>> Yleisö: lajitella vasen puoli.

428
00:17:40,570 --> 00:17:42,780
>> DAVID MALAN: Joten nyt minun täytyy lajitella
vasen puoli nämä kaverit.

429
00:17:42,780 --> 00:17:45,580
Koska taas olettaa itse
Tavoitteena on lajitella vasen puoli.

430
00:17:45,580 --> 00:17:46,440
Miten teet sen?

431
00:17:46,440 --> 00:17:49,140
Seuraa ohjeita, vaikka
vaikka teemme sen uudestaan.

432
00:17:49,140 --> 00:17:50,160
Joten lajitella vasen puoli.

433
00:17:50,160 --> 00:17:52,030
Nyt olen lajittelu nämä kaksi kaveria.

434
00:17:52,030 --> 00:17:53,563
Mitä seuraavaksi?

435
00:17:53,563 --> 00:17:54,510
>> Yleisö: lajitella vasen puoli.

436
00:17:54,510 --> 00:17:55,460
>> DAVID MALAN: lajitella vasen puoli.

437
00:17:55,460 --> 00:18:00,680
Joten nyt nämä, tämä paikka täällä,
on lista koko 1.

438
00:18:00,680 --> 00:18:01,365
Ja mikä sinun nimesi olikaan?

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

440
00:18:02,390 --> 00:18:03,690
>> DAVID MALAN: Prinsessa Daisy on täällä.

441
00:18:03,690 --> 00:18:07,470
Ja niin hän on jo järjestetty, koska
luettelo on koko 1.

442
00:18:07,470 --> 00:18:09,490
Mitä seuraavaksi tehdä?

443
00:18:09,490 --> 00:18:13,680
OK, palaa, koska luettelo on
koko 1, joka on pienempi kuin 2.

444
00:18:13,680 --> 00:18:14,320
Mikä sitten on seuraava askel?

445
00:18:14,320 --> 00:18:17,490
Ja nyt sinulla on sellainen
takapakkia mielessäsi.

446
00:18:17,490 --> 00:18:19,340
>> Lajitella oikea puoli, joka on -

447
00:18:19,340 --> 00:18:19,570
Mikä sinun nimesi on?

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

449
00:18:20,220 --> 00:18:20,980
>> DAVID MALAN: Linda.

450
00:18:20,980 --> 00:18:23,210
Ja niin mitä teemme nyt, että
meillä on lista koko 1?

451
00:18:23,210 --> 00:18:24,440
>> Yleisö: Return.

452
00:18:24,440 --> 00:18:24,760
>> DAVID MALAN: varovainen.

453
00:18:24,760 --> 00:18:29,540
Palaamme ensimmäinen, ja nyt kolmas
askel - ja jos olen sellainen kuvaavat sitä

454
00:18:29,540 --> 00:18:33,490
käsittää kaksi paikkaa nyt, nyt minä
on yhdistää nämä kaksi asiaa.

455
00:18:33,490 --> 00:18:35,530
Joten nyt valitettavasti elementtejä
ovat epäkunnossa.

456
00:18:35,530 --> 00:18:39,920
Mutta siitähän yhdistämismenettelystä
alkaa saada pakottavia.

457
00:18:39,920 --> 00:18:42,410
>> Joten jos te voisi nousta vain
hetki, aion tarvitsevat teitä,

458
00:18:42,410 --> 00:18:44,170
hetkellä vaiheeseen takana tuolin.

459
00:18:44,170 --> 00:18:46,480
Ja jos Linda, koska 2 on
pienempi kuin 4, mikset

460
00:18:46,480 --> 00:18:48,130
tulet noin ensin?

461
00:18:48,130 --> 00:18:48,690
Pysy siellä.

462
00:18:48,690 --> 00:18:50,520
Joten Linda, tulet noin ensin.

463
00:18:50,520 --> 00:18:53,820
>> Nyt todellisuudessa se on vain joukko
voisimme siirtää hänet reaaliajassa

464
00:18:53,820 --> 00:18:55,360
Tämän tuolin tällä paikalla.

465
00:18:55,360 --> 00:18:57,770
Joten kuvitella, että kesti jonkin jatkuvaa
useita vaiheita 1.

466
00:18:57,770 --> 00:18:58,480
Ja nyt -

467
00:18:58,480 --> 00:19:01,490
mutta meidän täytyy laittaa sinut
ensimmäisen sijainnin tässä.

468
00:19:01,490 --> 00:19:03,930
>> Ja nyt jos voisit tulla noin,
samoin, aiomme

469
00:19:03,930 --> 00:19:06,300
olla paikalla kaksi.

470
00:19:06,300 --> 00:19:09,120
Ja vaikka tämä tuntuu se
ottaen samalla, mitä mukavaa nyt

471
00:19:09,120 --> 00:19:14,710
että vasen puoli
vasen puoli on nyt järjestetty.

472
00:19:14,710 --> 00:19:18,010
Joten mikä oli seuraava askel, jos me nyt
kelaa edelleen tarina?

473
00:19:18,010 --> 00:19:18,980
>> Yleisö: Oikea puoli.

474
00:19:18,980 --> 00:19:19,900
>> DAVID MALAN: lajitella oikea puoli.

475
00:19:19,900 --> 00:19:21,320
Joten te täytyy tehdä tämä, samoin.

476
00:19:21,320 --> 00:19:23,510
Joten jos voisitte seisomaan
vain hetken?

477
00:19:23,510 --> 00:19:25,192
Ja mikä on nimesi?

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

479
00:19:25,540 --> 00:19:25,870
>> DAVID MALAN: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, joten Jess on nyt vasen
puolet oikealla puolella.

481
00:19:29,720 --> 00:19:31,400
Ja niin hän on luettelo koko 1.

482
00:19:31,400 --> 00:19:32,380
Hän ilmeisesti lajitellaan.

483
00:19:32,380 --> 00:19:33,070
Ja sinun nimesi olikaan?

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

485
00:19:33,630 --> 00:19:35,340
>> DAVID MALAN: Michelle on tietenkin
luettelo koko 1.

486
00:19:35,340 --> 00:19:36,050
Hän on jo järjestetty.

487
00:19:36,050 --> 00:19:38,690
Joten nyt taika tapahtuu,
yhdistämismenettelystä.

488
00:19:38,690 --> 00:19:39,790
Joten kuka tulee ensiksi?

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

490
00:19:41,560 --> 00:19:43,280
Joten jos voisit tulla ympäri takaisin.

491
00:19:43,280 --> 00:19:47,090
Tilaa meillä on käytettävissä hänen nyt
on oikeassa takana tuolin täällä.

492
00:19:47,090 --> 00:19:51,580
Ja nyt jos voisit palata sekä,
meillä on nyt, on selvää, kaksi

493
00:19:51,580 --> 00:19:53,810
puolikkaat, kukin kooltaan 2 -

494
00:19:53,810 --> 00:19:57,090
ja vain kuvaus vuoksi, jos
voisi tehdä vähän tilaa -

495
00:19:57,090 --> 00:19:59,780
yksi jäljellä puoli täällä, yksi
oikea puoli täällä.

496
00:19:59,780 --> 00:20:01,160
>> Kelaa edelleen tarina.

497
00:20:01,160 --> 00:20:02,270
Mikä vaihe on seuraava?

498
00:20:02,270 --> 00:20:03,030
>> Yleisö: Yhdistä.

499
00:20:03,030 --> 00:20:04,160
>> DAVID MALAN: Nyt meidän täytyy yhdistää.

500
00:20:04,160 --> 00:20:07,490
Joten OK, joten nyt onneksi meillä
vain vapautti neljä tuolia.

501
00:20:07,490 --> 00:20:11,480
Joten olemme käyttäneet kaksi kertaa enemmän muistia, mutta
voimme antaa flip-flopping välillä

502
00:20:11,480 --> 00:20:12,330
kaksi paneelit.

503
00:20:12,330 --> 00:20:14,190
Joten mikä numero on tulla ensin?

504
00:20:14,190 --> 00:20:14,850
Joten Michelle, tietenkin.

505
00:20:14,850 --> 00:20:16,680
Joten tulevat ympäri ja ottaa
Varmista paikkasi.

506
00:20:16,680 --> 00:20:19,120
Ja sitten numero 2 on ilmeisesti
seuraava, niin tulet tänne.

507
00:20:19,120 --> 00:20:21,520
Numero 4, numero 6.

508
00:20:21,520 --> 00:20:23,390
Ja vielä, vaikka siellä
vähän kävelyä mukana,

509
00:20:23,390 --> 00:20:26,010
todella, nämä voi tapahtua hetkessä,
siirtämällä yhtä -

510
00:20:26,010 --> 00:20:26,880
OK, hyvin pelattu.

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

512
00:20:28,350 --> 00:20:29,680
>> DAVID MALAN: Ja nyt me olemme
hyvässä kunnossa.

513
00:20:29,680 --> 00:20:34,910
Vasen puoli koko
tulo on nyt lajiteltu.

514
00:20:34,910 --> 00:20:37,370
Okei, niin nämä kaverit oli
etu minun -

515
00:20:37,370 --> 00:20:40,340
miten se lopulta kaikki tytöt
vasemmalle ja kaikki pojat oikealla?

516
00:20:40,340 --> 00:20:42,450
>> OK, joten kaverit vuoro nyt.

517
00:20:42,450 --> 00:20:44,680
Joten en opastaa
nämä vaiheet.

518
00:20:44,680 --> 00:20:46,550
Näemme, jos voimme hakea uudelleen
Sama pseudokoodina.

519
00:20:46,550 --> 00:20:50,050
Jos haluat mennä eteenpäin ja seisomaan,
ja te, minä annan sinulle mic.

520
00:20:50,050 --> 00:20:52,990
Katso jos et voi jäljitellä mitä
me vain teimme täällä

521
00:20:52,990 --> 00:20:53,880
muut listan loppuun.

522
00:20:53,880 --> 00:20:59,530
Kuka tarvitsee puhua ensin,
perusteella algoritmi?

523
00:20:59,530 --> 00:21:03,210
Joten selittää, mitä olet tekemässä ennen
teet jalka liikkeitä.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Okei, joten sillä
Olen vasen puoli

525
00:21:05,930 --> 00:21:07,790
vasen puoli, palaan.

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

527
00:21:08,730 --> 00:21:09,250
>> DAVID MALAN: Hyvä.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: Ja sitten -

529
00:21:10,350 --> 00:21:11,800
>> DAVID MALAN: Kuka tekee
mic mennä seuraavaksi?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: Seuraava numero.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Olen siis oikea puoli
ja vasen puoli

532
00:21:14,720 --> 00:21:17,830
vasen puoli, ja palaan.

533
00:21:17,830 --> 00:21:18,050
>> DAVID MALAN: Hyvä.

534
00:21:18,050 --> 00:21:18,550
Palaat.

535
00:21:18,550 --> 00:21:21,855
Joten nyt mitä seuraavaksi ylös sinulle kaksi?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Haluamme nähdä, kuka on pienempi.

537
00:21:23,740 --> 00:21:24,200
>> DAVID MALAN: Aivan.

538
00:21:24,200 --> 00:21:24,940
Haluamme yhdistää.

539
00:21:24,940 --> 00:21:27,590
Tilaa aiomme käyttää sulautua
sinut, vaikka he

540
00:21:27,590 --> 00:21:30,250
ilmeisesti lajitellaan jo aiomme
noudattaa samaa algoritmia.

541
00:21:30,250 --> 00:21:31,560
Kuka menee ensin takaisin?

542
00:21:31,560 --> 00:21:35,720
Joten 3, ja sitten 7.

543
00:21:35,720 --> 00:21:38,570
Ja nyt mic menee
Näiden kaverit, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Olen siis oikea puoli
vasen puoli, ja minun n on pienempi kuin

545
00:21:43,590 --> 00:21:45,048
1, joten olen juuri menossa ohi -

546
00:21:45,048 --> 00:21:46,380
>> DAVID MALAN: Hyvä.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Olen oikea puoli
oikea puoli oikea puoli, ja olen

548
00:21:49,450 --> 00:21:51,740
Lisäksi yksi henkilö, joten olen
aio palata.

549
00:21:51,740 --> 00:21:52,990
Joten nyt olemme yhdistäminen.

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

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Eli menemme takaisin.

552
00:21:56,150 --> 00:21:57,160
>> DAVID MALAN: Eli menet takaisin.

553
00:21:57,160 --> 00:21:59,200
Joten 5 menee ensin, sitten 8.

554
00:21:59,200 --> 00:22:01,240
Ja nyt yleisö, joka on
vaiheeseen meidän on nyt kelata

555
00:22:01,240 --> 00:22:02,200
takaisin mielessämme?

556
00:22:02,200 --> 00:22:02,940
>> Yleisö: Yhdistä.

557
00:22:02,940 --> 00:22:07,270
>> DAVID MALAN: yhdistäminen vasen puoli ja oikea
puolet alkuperäisestä vasen puoli.

558
00:22:07,270 --> 00:22:08,840
Joten nyt -

559
00:22:08,840 --> 00:22:10,520
ja vain tehdä tämän selväksi,
tehdä hieman tilaa

560
00:22:10,520 --> 00:22:11,690
välillä te kaksi kaveria.

561
00:22:11,690 --> 00:22:13,800
Joten nyt on kaksi listaa,
vasemmalle ja oikealle.

562
00:22:13,800 --> 00:22:18,320
Miten siis nyt sulautua te osaksi
eturivin paikkaa uudelleen?

563
00:22:18,320 --> 00:22:19,600
>> 3. menee ensin.

564
00:22:19,600 --> 00:22:20,850
Sitten 5, tietenkin.

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

566
00:22:23,110 --> 00:22:27,330
Sitten 7, ja nyt 8.

567
00:22:27,330 --> 00:22:28,710
OK, ja nyt me olemme?

568
00:22:28,710 --> 00:22:29,650
>> Yleisö: Ei tehty.

569
00:22:29,650 --> 00:22:32,440
>> DAVID MALAN: Ei tehty, koska
tietenkin, siellä on yksi askel jäljellä.

570
00:22:32,440 --> 00:22:35,720
Mutta jälleen kerran, syy Käytän tätä
sanastoa kuten "taaksepäin mielessäsi"

571
00:22:35,720 --> 00:22:37,160
se on koska se on todella
mitä tapahtuu.

572
00:22:37,160 --> 00:22:39,610
Menemme läpi kaikki nämä vaiheet,
mutta olemme tavallaan pysähtyen

573
00:22:39,610 --> 00:22:42,480
hetki, sukellus syvemmälle
algoritmi, pysähtyen hetkeksi,

574
00:22:42,480 --> 00:22:45,840
sukellus syvemmälle algoritmin, ja
nyt meillä on tavallaan taaksepäin meidän

575
00:22:45,840 --> 00:22:49,430
mielissä ja kumoa kaikki nämä kerrokset
että olemme tavallaan pitoon.

576
00:22:49,430 --> 00:22:51,790
>> Meillä on nyt siis kaksi luetteloa koko 4.

577
00:22:51,790 --> 00:22:54,790
Jos te voisi nousta viimeisen kerran
ja tehdä vähän tilaa täällä

578
00:22:54,790 --> 00:22:57,230
tehdä selväksi, että tämä on vasen
puoleen alkuperäisestä,

579
00:22:57,230 --> 00:22:58,620
oikeus puolet alkuperäisestä.

580
00:22:58,620 --> 00:23:01,060
Kuka ensimmäinen numero että
täytyy vetää takaisin?

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

582
00:23:01,870 --> 00:23:03,230
>> Joten laitoimme Michelle täällä.

583
00:23:03,230 --> 00:23:05,080
Ja kuka on numero 2?

584
00:23:05,080 --> 00:23:06,440
Numero 2 syttyy takaisin samoin.

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

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

587
00:23:08,510 --> 00:23:16,570
Numero 4, numero 5, numero 6,
numero 7 ja numero 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, joten se tuntui paljon
vaiheita, varmasti.

589
00:23:18,850 --> 00:23:22,390
Mutta nyt katsotaanpas jos emme voi vahvistaa
eräänlainen intuitiivisesti, että tämä

590
00:23:22,390 --> 00:23:26,190
algoritmi pohjimmiltaan, erityisesti
n saa todella suuri, kuten olemme nähneet

591
00:23:26,190 --> 00:23:29,170
kanssa animaatioita, on
pohjimmiltaan nopeammin.

592
00:23:29,170 --> 00:23:33,400
Joten Väitän tämä algoritmi pahimmassa
tapauksessa ja jopa parhaassa tapauksessa

593
00:23:33,400 --> 00:23:36,160
on iso O n kertaa log n.

594
00:23:36,160 --> 00:23:39,160
Eli siellä on joitakin osa tätä
algoritmi, joka vie n askelta, mutta

595
00:23:39,160 --> 00:23:43,110
on toinen näkökohta jossain
että iteraatio, että kiehkura, että

596
00:23:43,110 --> 00:23:44,410
otetaan log n vaiheet.

597
00:23:44,410 --> 00:23:49,154
Voimmeko laittaa sormi mitä ne
kaksi numeroa viittaavat?

598
00:23:49,154 --> 00:23:51,320
No, jos -

599
00:23:51,320 --> 00:23:54,160
Minne mic mennä?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Olisiko log n on
rikkomatta meidät kahteen -

601
00:23:58,660 --> 00:23:59,630
jakamalla kaksi lähinnä.

602
00:23:59,630 --> 00:24:00,120
>> DAVID MALAN: Aivan.

603
00:24:00,120 --> 00:24:03,000
Aina näemme missään ollen algoritmi
mennessä siellä on ollut tämä malli

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

605
00:24:04,200 --> 00:24:05,700
Ja se yleensä vähenee
jotain, joka on

606
00:24:05,700 --> 00:24:07,100
logaritminen, logaritmina 2.

607
00:24:07,100 --> 00:24:10,180
Mutta se voisi todella olla mitä tahansa,
mutta logaritmi 2.

608
00:24:10,180 --> 00:24:11,330
>> Mutta mites n?

609
00:24:11,330 --> 00:24:14,550
Näen, että meillä sellainen jaettu sinua
kaverit - jakaa teille, jakaa teille,

610
00:24:14,550 --> 00:24:15,910
jakaa teille, jakaa teille.

611
00:24:15,910 --> 00:24:18,760
Mistä lopulta tulee?

612
00:24:18,760 --> 00:24:19,810
>> Joten se yhdistämistä.

613
00:24:19,810 --> 00:24:20,610
Koska mieti sitä.

614
00:24:20,610 --> 00:24:25,420
Kun yhdistät kahdeksan ihmistä yhdessä,
jolloin puolet on asetettu neljä

615
00:24:25,420 --> 00:24:27,770
ja toinen puoli ovat toinen
Neljä, miten edetä

616
00:24:27,770 --> 00:24:28,820
noin tekee yhdistäminen?

617
00:24:28,820 --> 00:24:30,830
No, te teitte sen
melko intuitiivisesti.

618
00:24:30,830 --> 00:24:34,140
>> Mutta jos sen sijaan teki siitä hieman
suunnitelmallisesti, olisin suunnattu

619
00:24:34,140 --> 00:24:38,090
vasemmanpuoleisin henkilö ensin minun vasen
käsi, huomautti vasemmalla henkilö

620
00:24:38,090 --> 00:24:42,080
Kyseisen puolet minun oikealle puolelleni, ja
vain myöhemmin käveli

621
00:24:42,080 --> 00:24:46,990
lista, osoittaen pienimmän alkion
joka kerta, liikkuvat minun sormella ja

622
00:24:46,990 --> 00:24:48,970
yli tarpeen koko lista.

623
00:24:48,970 --> 00:24:51,890
Mutta mitä näppäintä tästä sulautuvan
prosessi on olen vertaamalla näitä paria

624
00:24:51,890 --> 00:24:53,460
elementtejä.

625
00:24:53,460 --> 00:24:57,270
Oikean puolen ja vasemman
puoli, en kertaakaan vetäytymistä.

626
00:24:57,270 --> 00:25:00,570
>> Joten yhdistäminen on itse tuossa
enintään n askelta.

627
00:25:00,570 --> 00:25:03,250
Ja kuinka monta kertaa olen
tehdä, että yhdistäminen?

628
00:25:03,250 --> 00:25:07,150
No, enintään n, ja me vain
näki, että lopullinen yhdistämisen.

629
00:25:07,150 --> 00:25:13,120
Ja niin jos teet jotain, joka vie
log n askelta n kertaa, tai päinvastoin,

630
00:25:13,120 --> 00:25:15,210
se tulee antamaan meille n kertaa log n.

631
00:25:15,210 --> 00:25:16,310
>> Ja miksi tämä on parempi?

632
00:25:16,310 --> 00:25:19,600
No, jos me jo tiedämme, että log
n on parempi kuin n - eikö?

633
00:25:19,600 --> 00:25:22,590
Näimme binäärihaku, puhelinluettelo
Esimerkiksi log n oli ehdottomasti

634
00:25:22,590 --> 00:25:23,760
parempi kuin lineaarinen.

635
00:25:23,760 --> 00:25:28,420
Joten se tarkoittaa n kertaa log n on
ehdottomasti parempi kuin n kertaa toisen

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

637
00:25:30,390 --> 00:25:32,400
Ja sitähän me lopulta tuntuu.

638
00:25:32,400 --> 00:25:34,928
>> Joten aplodit, jos
Voisimme nämä kaverit.

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

640
00:25:38,920 --> 00:25:41,550
>> DAVID MALAN: Ja jakaus lahjat -
voi pitää numerot,

641
00:25:41,550 --> 00:25:44,010
jos haluat.

642
00:25:44,010 --> 00:25:45,620
Ja jakaus lahja, kuten tavallista.

643
00:25:45,620 --> 00:25:47,290
Niin, ja me lähetämme sinulle
kuvamateriaalia, Michelle.

644
00:25:47,290 --> 00:25:48,343
Kiitos.

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

646
00:25:49,250 --> 00:25:50,400
Auta itseäsi stressipallo.

647
00:25:50,400 --> 00:25:54,110
>> Ja haluan vetää, sillä välin,
ystävämme Rob Bowden tarjota

648
00:25:54,110 --> 00:25:59,520
hieman erilaisen näkökulman tähän,
koska voit ajatella näitä

649
00:25:59,520 --> 00:26:01,280
vaiheet tapahtuu hieman
eri tavalla.

650
00:26:01,280 --> 00:26:04,750
Itse asiassa, set-up, mitä Rob on noin
näyttää meille olettaa, että olemme

651
00:26:04,750 --> 00:26:09,030
jo jakamista ja
iso lista kahdeksaan pieniä luetteloita,

652
00:26:09,030 --> 00:26:10,570
kukin koko 1.

653
00:26:10,570 --> 00:26:13,350
>> Joten me muutumme pseudokoodina
hieman vain tavallaan saada aikaa

654
00:26:13,350 --> 00:26:15,320
ydinajatuksena miten yhdistäminen toimivat.

655
00:26:15,320 --> 00:26:17,600
Mutta ajoaika mitä
hän on aikeissa tehdä, on edelleen

656
00:26:17,600 --> 00:26:19,110
olemaan sama.

657
00:26:19,110 --> 00:26:23,540
Ja vielä, set-up on, että hän on
alkanut kahdeksan luettelot koko 1.

658
00:26:23,540 --> 00:26:27,730
Joten olet jäänyt osa, jossa hän on
todella tehneet log n, log n, log n

659
00:26:27,730 --> 00:26:31,205
jakamalla tulo.

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

661
00:26:32,120 --> 00:26:33,615
>> -Se on se ensimmäinen vaihe.

662
00:26:33,615 --> 00:26:38,270
Vaiheessa kaksi, toistuvasti
yhdistää paria luetteloita.

663
00:26:38,270 --> 00:26:39,210
>> DAVID MALAN: Hm.

664
00:26:39,210 --> 00:26:41,270
Vain ääni on tulossa
pois minun tietokone.

665
00:26:41,270 --> 00:26:42,520
Kokeillaan tätä uudelleen.

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

667
00:26:45,330 --> 00:26:48,310
>> -Aivan mielivaltaisesti valita, -
Nyt meillä on neljä luettelot.

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

669
00:26:51,590 --> 00:26:52,120
Lue ennen.

670
00:26:52,120 --> 00:26:53,040
>> DAVID MALAN: Siellä mennään.

671
00:26:53,040 --> 00:27:00,510
>> -Yhdistäminen 108 ja 15, päädymme
kanssa luettelon 15, 108.

672
00:27:00,510 --> 00:27:07,170
Yhdistäminen 50 ja 4, me
päätyä 4 50.

673
00:27:07,170 --> 00:27:12,990
Yhdistäminen 8 ja 42, me
päätyä 8, 42.

674
00:27:12,990 --> 00:27:19,970
Ja yhdistämällä 23 ja 16, me
päätyä 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Nyt kaikki luettelot ovat kooltaan 2.

676
00:27:23,270 --> 00:27:26,690
Huomaa, että kukin
neljä luettelot lajitellaan.

677
00:27:26,690 --> 00:27:29,450
Joten voimme aloittaa sulautuvan
paria luettelot uudelleen.

678
00:27:29,450 --> 00:27:38,420
Yhdistäminen 15 ja 108 ja 4 ja 50, me
toteuttaa ensin 4, sitten 15, sitten

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

680
00:27:41,500 --> 00:27:50,610
Yhdistäminen 8, 42 ja 16, 23, ensin ottaa
8, sitten 16, sitten 23,

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

682
00:27:52,700 --> 00:27:57,600
>> Joten nyt meillä on vain kaksi luetteloa koko
4, joista kukin on järjestetty.

683
00:27:57,600 --> 00:28:01,170
Nyt siis yhdistää nämä kaksi luetteloa.

684
00:28:01,170 --> 00:28:11,835
Ensin otamme 4, niin otamme
8, sitten otamme 15, sitten 16, sitten

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

686
00:28:19,456 --> 00:28:19,872
>> [END VIDEOTOISTOSTA]

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: Jälleen ilmoituksen, hän ei koskaan
kosketti tietyn kuppi useamman kuin yhden kerran

688
00:28:23,430 --> 00:28:24,860
jälkeen etenee pidemmälle.

689
00:28:24,860 --> 00:28:26,200
Joten hän ei ole koskaan toistuvan.

690
00:28:26,200 --> 00:28:29,850
Niin hän on aina siirtymässä puolelle,
ja se jos saimme n.

691
00:28:29,850 --> 00:28:33,290
>> Miksi ei anna minun vetää yksi animaatio
että näimme aiemmin, mutta tällä kertaa

692
00:28:33,290 --> 00:28:35,110
keskitytään vain merge sort.

693
00:28:35,110 --> 00:28:38,030
Anna minun mennä eteenpäin ja zoomata
sisään täällä.

694
00:28:38,030 --> 00:28:42,530
Ensinnäkin haluan valita satunnainen tulo,
tämä korostuu, ja voit tavallaan nähdä

695
00:28:42,530 --> 00:28:46,600
mitä otimme itsestäänselvyytenä, aiemmin,
yhdistää tavallaan todella tekee.

696
00:28:46,600 --> 00:28:50,330
>> Niin huomaat että saat nämä puolikkaat tai
neljännesvuoden tai näiden kahdeksasosaa

697
00:28:50,330 --> 00:28:53,140
ongelma, että yhtäkkiä
alkaa ottaa hyvässä kunnossa.

698
00:28:53,140 --> 00:28:57,070
Ja lopulta, näet at
aivan lopussa, että bam,

699
00:28:57,070 --> 00:28:58,860
kaikki on sulautunut yhteen.

700
00:28:58,860 --> 00:29:01,690
>> Joten nämä ovat vain kolme eri
vie samaan ideaan.

701
00:29:01,690 --> 00:29:05,980
Mutta avain oivalluksia, kuten kuilu
ja valloittaa aivan ensiluokkainen,

702
00:29:05,980 --> 00:29:10,640
oli, että päätimme jotenkin jakaa
Ongelma tulee jotain suurta, osaksi

703
00:29:10,640 --> 00:29:14,760
jotain tavallaan sama henki,
mutta pienempiä ja pienempiä

704
00:29:14,760 --> 00:29:15,660
ja pienempiä.

705
00:29:15,660 --> 00:29:18,420
>> Nyt toinen hauska tapa tavallaan ajatella
näistä, vaikka se ei ole

706
00:29:18,420 --> 00:29:20,520
aio antaa teille saman intuitiivinen
ymmärtäminen, on

707
00:29:20,520 --> 00:29:21,640
seuraava animaatio.

708
00:29:21,640 --> 00:29:25,400
Joten tämä on video joku koota
että liittyvät eri

709
00:29:25,400 --> 00:29:29,970
äänet eri toimintojen
lisäyslajittelu varten yhdistäminen lajitella ja

710
00:29:29,970 --> 00:29:31,150
ja pari muuta.

711
00:29:31,150 --> 00:29:32,330
Joten hetki, aion lyödä Play.

712
00:29:32,330 --> 00:29:33,600
Se on noin minuutin pituinen.

713
00:29:33,600 --> 00:29:37,410
Ja vaikka et voi vielä nähdä
kuvioita tapahtuu, tällä kertaa voit

714
00:29:37,410 --> 00:29:41,420
myös kuulla, miten nämä algoritmit ovat
suorittaa eri tavoin ja

715
00:29:41,420 --> 00:29:43,950
hieman erilaisia ​​kuvioita.

716
00:29:43,950 --> 00:29:45,830
>> Tämä on lisäyslajittelu.

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

718
00:29:50,400 --> 00:29:52,400
>> DAVID MALAN: Se taas yrittää
lisätä jokaisen elementin

719
00:29:52,400 --> 00:29:52,900
siitä, mihin se kuuluu.

720
00:29:52,900 --> 00:29:54,628
Tämä on kupla tavallaan.

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

722
00:30:10,097 --> 00:30:13,630
>> DAVID MALAN: Ja voit tavallaan tuntuu
miten suhteellisen vähän työtä se tekee

723
00:30:13,630 --> 00:30:15,834
kussakin vaiheessa.

724
00:30:15,834 --> 00:30:20,470
Tämä on mitä tediousness kuulostaa.

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

726
00:30:21,472 --> 00:30:25,222
>> DAVID MALAN: Tämä on valinta lajitella,
jossa valitse elementti haluamme by

727
00:30:25,222 --> 00:30:28,845
läpi uudestaan ​​ja uudestaan ​​ja uudestaan
ja laittoi pallon alussa.

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

729
00:30:37,674 --> 00:30:43,970
>> DAVID MALAN: Tämä on yhdistää tavallaan, joka
voit todella alkaa tuntea.

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

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

732
00:30:54,770 --> 00:30:58,395
>> DAVID MALAN: Jotain nimeltään gnome
lajitella, joita emme ole katsonut.

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

734
00:31:13,630 --> 00:31:17,910
>> DAVID MALAN: Niin anna minun nähdä, nyt
hajamielinen kun toivottavasti ovat by

735
00:31:17,910 --> 00:31:21,110
musiikkia, jos voin luistaa hieman
vähän matematiikkaa täällä.

736
00:31:21,110 --> 00:31:24,850
Joten on neljäsosa tavalla, että voimme
miettiä, mitä se tarkoittaa, että nämä

737
00:31:24,850 --> 00:31:29,210
toimintoja nopeammin kuin niitä
että olemme nähneet ennen.

738
00:31:29,210 --> 00:31:32,470
Ja jos olet tulossa kurssin
matematiikan tausta, voit

739
00:31:32,470 --> 00:31:36,030
oikeastaan ​​tiedä ehkä jo, että olet
voi isku aikavälillä tähän tekniikkaan -

740
00:31:36,030 --> 00:31:40,400
eli rekursio, toiminto
että jotenkin kutsuu itseään.

741
00:31:40,400 --> 00:31:44,780
>> Ja vielä, muistaa, että yhdistäminen lajitella
pseudokoodina oli rekursiivinen mielessä

742
00:31:44,780 --> 00:31:48,460
että yksi Merge sort askeleet
oli soittaa tavallaan -

743
00:31:48,460 --> 00:31:49,740
se on, itse.

744
00:31:49,740 --> 00:31:52,480
Mutta onneksi, koska pidimme
soittamalla lajitella tai yhdistää lajitella,

745
00:31:52,480 --> 00:31:55,880
Erityisesti on pienempiä
ja pienempi lista, me lopulta

746
00:31:55,880 --> 00:32:00,005
pohjansa ansiosta mitä me kutsumme
pohja tapauksessa koodattu niin, että

747
00:32:00,005 --> 00:32:04,270
sanoi, että jos lista on pieni, alle 2
siinä tapauksessa, palaa heti.

748
00:32:04,270 --> 00:32:07,550
Jos meillä ei ole, että erikoistapaus,
algoritmi olisi koskaan pohja pois,

749
00:32:07,550 --> 00:32:11,010
ja sinulla olisi todellakin päästä
päättymättömään silmukkaan todella ikuisesti.

750
00:32:11,010 --> 00:32:14,330
>> Mutta oletetaan, että halusimme nyt laittaa
joitakin numeroita tässä, jälleen käyttäen n

751
00:32:14,330 --> 00:32:15,660
kuin koko panos.

752
00:32:15,660 --> 00:32:18,680
Ja halusin kysyä teiltä, ​​mitä
kokonaisaika mukana

753
00:32:18,680 --> 00:32:19,800
käynnissä Yhdistämisen tavallaan?

754
00:32:19,800 --> 00:32:22,960
Tai yleisemmin, mitä
kustannukset sen ajoissa?

755
00:32:22,960 --> 00:32:24,730
>> No se on melko helppo mitata sitä.

756
00:32:24,730 --> 00:32:29,010
Jos n on pienempi kuin 2, aikaa mukana
lajittelussa n elementtejä,

757
00:32:29,010 --> 00:32:30,480
jossa n on 2, on 0.

758
00:32:30,480 --> 00:32:31,410
Koska me vain palata.

759
00:32:31,410 --> 00:32:32,510
Ei ole tehtävää.

760
00:32:32,510 --> 00:32:35,660
Nyt luultavasti, ehkä se on yksi askel tai kaksi
vaiheet selvittää määrä

761
00:32:35,660 --> 00:32:38,420
työtä, mutta se on tarpeeksi lähellä 0, että
Olen juuri menossa sanoa mitään työtä ei

762
00:32:38,420 --> 00:32:40,940
vaadita, jos lista on niin pieni
on mielenkiinnoton.

763
00:32:40,940 --> 00:32:42,580
>> Mutta tämä tapaus on mielenkiintoinen.

764
00:32:42,580 --> 00:32:47,320
Rekursiivinen tapaus oli haara
pseudokoodina että mainittu muuta, sort

765
00:32:47,320 --> 00:32:52,000
vasen puoli, lajitella oikea
puoli, yhdistää kaksi puolikasta.

766
00:32:52,000 --> 00:32:55,530
Nyt miksi tämä ilmaus
edustaa että kuluja?

767
00:32:55,530 --> 00:32:58,690
No, T n vain sitä,
aikaa selvittää n elementtejä.

768
00:32:58,690 --> 00:33:03,070
Ja sitten oikealla puolella
yhtäläisyysmerkkiä siellä, T n jaettu

769
00:33:03,070 --> 00:33:06,600
2 viittaa kustannukset mitä?

770
00:33:06,600 --> 00:33:07,570
Lajittelu vasen puoli.

771
00:33:07,570 --> 00:33:10,990
Muut T n jaettuna 2 on
oletettavasti viitaten kustannukset

772
00:33:10,990 --> 00:33:12,390
lajitella oikea puoli.

773
00:33:12,390 --> 00:33:14,590
>> Ja sitten plus n?

774
00:33:14,590 --> 00:33:15,420
Onko yhdistämistä.

775
00:33:15,420 --> 00:33:19,120
Koska jos sinulla on kaksi listaa, yksi
koko n yli 2 ja toisen koko on n

776
00:33:19,120 --> 00:33:22,580
yli 2, sinun on olemukseltaan
jokainen näistä seikoista, kuten Rob

777
00:33:22,580 --> 00:33:24,990
kosketti molempia kupit, ja vain
kuten jo jokaisessa

778
00:33:24,990 --> 00:33:26,310
vapaaehtoiset lavalla.

779
00:33:26,310 --> 00:33:28,790
Joten n on kustannuksella yhdistämistä.

780
00:33:28,790 --> 00:33:31,780
>> Nyt valitettavasti tämä kaava
on myös itse rekursiivinen.

781
00:33:31,780 --> 00:33:36,390
Joten jos kysyi, jos n on vaikkapa
16, jos siellä on 16 ihmistä lavalla

782
00:33:36,390 --> 00:33:40,670
tai 16 kupillista video, kuinka monta yhteensä
vaiheet kestää järjestellä

783
00:33:40,670 --> 00:33:41,550
Yhdistäminen lajitella?

784
00:33:41,550 --> 00:33:45,790
Se on oikeastaan ​​ole selvää vastausta,
koska nyt sinulla on tavallaan

785
00:33:45,790 --> 00:33:48,500
rekursiivisesti vastata tähän kaavaan.

786
00:33:48,500 --> 00:33:51,190
>> Mutta se on OK, koska haluan ehdottaa
että teemme seuraavat.

787
00:33:51,190 --> 00:33:56,670
Aikaa mukana lajitella 16 henkilöä tai
16 kuppia tulee olla edustettuna

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

789
00:33:58,020 --> 00:34:01,400
Mutta joka vastaa saamiemme
edellinen kaava, 2 kertaa enemmän

790
00:34:01,400 --> 00:34:04,780
aikaa kuluu lajitella
8 kuppia plus 16.

791
00:34:04,780 --> 00:34:08,590
Ja vielä, plus 16 on aika yhdistää,
ja kaksi kertaa T 8 on

792
00:34:08,590 --> 00:34:10,790
aikaa selvittää vasen puoli ja oikea puoli.

793
00:34:10,790 --> 00:34:11,989
>> Mutta jälleen kerran, tämä ei riitä.

794
00:34:11,989 --> 00:34:13,210
Meidän täytyy sukeltaa syvemmälle.

795
00:34:13,210 --> 00:34:16,409
Tämä tarkoittaa, että meidän on vastattava
kysymys, mikä on T 8?

796
00:34:16,409 --> 00:34:19,610
No T 8 on vain 2
kertaa T 4 +8.

797
00:34:19,610 --> 00:34:20,520
No, mitä T 4?

798
00:34:20,520 --> 00:34:23,780
T 4 on vain 2 kertaa T 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
No, mitä T 2?

800
00:34:25,489 --> 00:34:29,030
T 2 on vain 2 kertaa T 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> Ja vielä, olemme tavallaan saada
juuttunut tämä sykli.

802
00:34:31,940 --> 00:34:34,790
Mutta se on osumassa, että
ns base tapauksessa.

803
00:34:34,790 --> 00:34:37,310
Koska mitä T 1, ei me väitämme?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Joten nyt vihdoin, voimme työskennellä taaksepäin.

806
00:34:39,730 --> 00:34:44,290
>> Jos T 1 on 0, voin nyt palata edelliselle
linja tämä kaveri täällä, ja voin

807
00:34:44,290 --> 00:34:46,330
plug in 0 T 1.

808
00:34:46,330 --> 00:34:51,770
Niin se tarkoittaa, se vastaa 2 kertaa nolla,
joka tunnetaan myös 0, plus 2.

809
00:34:51,770 --> 00:34:53,739
Ja niin, että koko ilmaisua on 2.

810
00:34:53,739 --> 00:34:58,740
>> Nyt jos otan T 2, jonka vastaus
on 2, kytke se keskilinjaa, T

811
00:34:58,740 --> 00:35:02,740
4, joka antaa minulle 2 kertaa
2 plus 4, joten 8.

812
00:35:02,740 --> 00:35:07,080
Jos en kytke 8 edelliseen
line, joka antaa minulle 2 kertaa 8, 16.

813
00:35:07,080 --> 00:35:12,470
Ja jos me sitten jatkaa, että
24 lisäämällä, 16, me vihdoinkin

814
00:35:12,470 --> 00:35:13,820
arvo 64.

815
00:35:13,820 --> 00:35:18,480
>> Nyt sinänsä tavallaan puhuu
mitään n merkintä,

816
00:35:18,480 --> 00:35:20,700
iso O, omega, että olemme
puhuneet.

817
00:35:20,700 --> 00:35:24,890
Mutta näyttää siltä, ​​että 64 on todellakin
16, koko syöttö,

818
00:35:24,890 --> 00:35:27,110
logaritmi 2 16.

819
00:35:27,110 --> 00:35:30,200
Ja jos tämä on hieman tuntematon, vain
muistelen, ja se tulee takaisin

820
00:35:30,200 --> 00:35:30,700
sinulle lopulta.

821
00:35:30,700 --> 00:35:33,775
Jos tämä on logaritmina 2, se on kuin 2
nostetaan mitä saat 16?

822
00:35:33,775 --> 00:35:36,380
Voi, se on 4, niin se on 16 kertaa 4.

823
00:35:36,380 --> 00:35:39,380
>> Ja vielä, se ei ole iso juttu, jos tämä
on eräänlainen utuinen muisti nyt.

824
00:35:39,380 --> 00:35:43,720
Mutta nyt, ottaa uskossa
että 16 log 16 on 64.

825
00:35:43,720 --> 00:35:46,590
Ja niin tosiaan, tämä yksinkertainen järki
Tarkista, olemme vahvistaneet -

826
00:35:46,590 --> 00:35:48,250
mutta ei osoittautunut muodollisesti -

827
00:35:48,250 --> 00:35:52,800
että ajoaika Yhdistämisen
sort on todellakin n log n.

828
00:35:52,800 --> 00:35:53,790
>> Joten ei paha.

829
00:35:53,790 --> 00:35:57,260
Se on ehdottomasti parempi kuin
algoritmeja olemme nähneet tähän mennessä, ja

830
00:35:57,260 --> 00:36:00,710
se on koska olemme velkarahalla, yksi,
tekniikkaa kutsutaan rekursion.

831
00:36:00,710 --> 00:36:03,880
Mutta mielenkiintoisempaa kuin, että
käsitettä jakamalla ja valloittaa.

832
00:36:03,880 --> 00:36:07,460
Jälleen todella viikolla 0 kamaa, että
jo nyt on toistuva

833
00:36:07,460 --> 00:36:08,740
enemmän pakottavia tavalla.

834
00:36:08,740 --> 00:36:11,750
>> Nyt hauskaa vähän liikuntaa, jos olet
koskaan tehnyt tätä - ja luultavasti

835
00:36:11,750 --> 00:36:14,660
ei olisi, koska tavallaan normaalia
ihmiset eivät usko tähän.

836
00:36:14,660 --> 00:36:20,650
Mutta jos menen google.com ja jos
Haluan oppia jotain

837
00:36:20,650 --> 00:36:22,356
rekursio, Anna.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Naurua]

840
00:36:29,058 --> 00:36:32,030
[Naurua]

841
00:36:32,030 --> 00:36:33,385
DAVID MALAN: Bad vitsi hitaasti leviää.

842
00:36:33,385 --> 00:36:34,450
[Naurua]

843
00:36:34,450 --> 00:36:36,970
DAVID MALAN: Vain siinä tapauksessa, että se on siellä.

844
00:36:36,970 --> 00:36:38,710
En kirjoittaa sen väärin,
ja siellä on vitsi.

845
00:36:38,710 --> 00:36:40,810
Selvä.

846
00:36:40,810 --> 00:36:42,950
Selitä sitä ihmisille vieressäsi jos
Se ei ole aivan napsautetaan vielä.

847
00:36:42,950 --> 00:36:47,650
Mutta rekursio yleisemmin viitataan
prosessia toiminto soittaa

848
00:36:47,650 --> 00:36:51,430
itse, tai yleisemmin, väliseinä
ongelma jotain, joka voi olla

849
00:36:51,430 --> 00:36:56,220
ratkaista vähitellen ratkaisemalla identtisiä
edustaja ongelmia.

850
00:36:56,220 --> 00:36:58,400
>> No, vaihtohammaspyöriä
vain hetken.

851
00:36:58,400 --> 00:37:00,840
Haluamme lopettaa tiettyjen cliffhangers,
joten aloitamme asettaa

852
00:37:00,840 --> 00:37:05,870
vaiheessa useita minuutteja,
on hyvin yksinkertainen idea -

853
00:37:05,870 --> 00:37:07,620
että vaihtava kahdesta osasta, eikö?

854
00:37:07,620 --> 00:37:10,040
Kaikki nämä algoritmit olemme olleet
puhumme parin viime

855
00:37:10,040 --> 00:37:12,420
luentoja osallistuu noin
tavallaan vaihtamalla.

856
00:37:12,420 --> 00:37:14,630
Tänään se oli visualisoitu niitä saada
ylös niiden puheenjohtajat ja

857
00:37:14,630 --> 00:37:18,570
käveleminen, mutta koodi, olisimme
ota elementti yhdestä array

858
00:37:18,570 --> 00:37:20,370
ja plop se toiseen.

859
00:37:20,370 --> 00:37:21,880
>> Miten siis edetä näin?

860
00:37:21,880 --> 00:37:24,850
No, anna minun mennä eteenpäin ja kirjoittaa
nopea ohjelma täältä.

861
00:37:24,850 --> 00:37:31,600
Aion mennä eteenpäin ja tehdä
tätä seuraava.

862
00:37:31,600 --> 00:37:33,910
Kutsun tätä -

863
00:37:33,910 --> 00:37:38,070
mitä haluamme kutsua tämä?

864
00:37:38,070 --> 00:37:38,650
>> Oikeastaan ​​ei.

865
00:37:38,650 --> 00:37:39,420
Minäpä taaksepäin.

866
00:37:39,420 --> 00:37:41,220
En halua tehdä sitä
jännitysnäytelmä vielä.

867
00:37:41,220 --> 00:37:42,270
Se pilaa hauskaa.

868
00:37:42,270 --> 00:37:43,600
Tehdään tämä sijaan.

869
00:37:43,600 --> 00:37:47,430
>> Oletetaan, että haluan kirjoittaa hieman
ohjelma ja että nyt kattaa tämän

870
00:37:47,430 --> 00:37:48,700
Ajatus rekursio.

871
00:37:48,700 --> 00:37:50,370
Olen sellainen sai ennen itseäni siellä.

872
00:37:50,370 --> 00:37:51,420
Aion tehdä seuraavasti.

873
00:37:51,420 --> 00:38:00,220
>> Ensinnäkin, nopea ovat standardin io.h,
sekä include of cs50.h.

874
00:38:00,220 --> 00:38:03,200
Ja sitten aion mennä eteenpäin
ja julistaa int main void

875
00:38:03,200 --> 00:38:04,360
tavalliseen tapaan.

876
00:38:04,360 --> 00:38:07,920
Tajusin olen väärin nimetty tiedosto, niin
haluan vain lisätä. c laajennus täällä niin

877
00:38:07,920 --> 00:38:09,510
että voimme kääntää sen oikein.

878
00:38:09,510 --> 00:38:10,970
Aloittaa tämän toiminnon pois päältä.

879
00:38:10,970 --> 00:38:13,290
>> Ja toiminto Haluan kirjoittaa, varsin
yksinkertaisesti, on yksi, joka kysyy

880
00:38:13,290 --> 00:38:16,210
käyttäjän numero ja lisää jopa
kaikki numerot välillä että

881
00:38:16,210 --> 00:38:19,920
numero ja vaikkapa 0.

882
00:38:19,920 --> 00:38:22,510
Ensin aion mennä eteenpäin
ja julistaa int n.

883
00:38:22,510 --> 00:38:24,760
Sitten voin kopioida koodia että
olemme käyttäneet jonkin aikaa.

884
00:38:24,760 --> 00:38:26,660
Vaikka jokin on totta.

885
00:38:26,660 --> 00:38:28,000
Tulen takaisin hetken päästä.

886
00:38:28,000 --> 00:38:29,010
>> Mitä haluat tehdä?

887
00:38:29,010 --> 00:38:33,460
Haluan sanoa printf positiivinen
kokonaisluku kiitos.

888
00:38:33,460 --> 00:38:36,130
Ja sitten aion
sanoa n saa saada int.

889
00:38:36,130 --> 00:38:38,800
Joten jälleen, jotkut boilerplate koodi
että olemme käyttäneet ennen.

890
00:38:38,800 --> 00:38:40,810
Ja aion tehdä tämän
kun n on pienempi kuin 1.

891
00:38:40,810 --> 00:38:44,120
Joten näin varmistetaan, että käyttäjä
antaa minulle positiivinen kokonaisluku.

892
00:38:44,120 --> 00:38:45,490
>> Ja nyt aion tehdä seuraavaa.

893
00:38:45,490 --> 00:38:51,020
Haluan lisätä jopa kaikki numerot
välillä 1 ja ja n, tai 0 ja n,

894
00:38:51,020 --> 00:38:52,570
yhtäpitävästi, saada kokonaissummasta.

895
00:38:52,570 --> 00:38:55,100
Joten iso sigma symboli
että saatatte muistaa.

896
00:38:55,100 --> 00:38:59,050
Joten aion tehdä tämän ensimmäistä tehtäväänsä
toiminto nimeltään sigma,

897
00:38:59,050 --> 00:39:06,030
kulkee sen n, ja sitten aion
sanovat printf, vastaus on oikeassa.

898
00:39:06,030 --> 00:39:08,180
>> Joten lyhyt, saan ja
int käyttäjältä.

899
00:39:08,180 --> 00:39:09,280
Varmistan se on positiivista.

900
00:39:09,280 --> 00:39:12,700
Julistan muuttuja nimeltä vastausta
int ja säilytä se tuotto

901
00:39:12,700 --> 00:39:15,610
arvo sigma, ohimennen n tulona.

902
00:39:15,610 --> 00:39:17,060
Ja sitten tulostaa, että vastaus.

903
00:39:17,060 --> 00:39:19,550
>> Valitettavasti, vaikka sigma kuulostaa
jotain, joka voisi olla

904
00:39:19,550 --> 00:39:24,040
math.h tiedosto, sen julistuksen,
se ei todellisuudessa ole.

905
00:39:24,040 --> 00:39:24,690
Niin se on OK.

906
00:39:24,690 --> 00:39:26,170
Voin toteuttaa tämän itse.

907
00:39:26,170 --> 00:39:29,160
Aion toteuttaa toiminto nimeltään
sigma, ja se tulee ottaa

908
00:39:29,160 --> 00:39:29,900
parametri -

909
00:39:29,900 --> 00:39:32,100
Haluan vain kutsua sitä m, vain
joten se on erilainen.

910
00:39:32,100 --> 00:39:35,910
Ja sitten täällä, aion sanoa,
hyvin, jos m on pienempi kuin 1 - tämä on

911
00:39:35,910 --> 00:39:38,180
erittäin mielenkiinnoton ohjelma.

912
00:39:38,180 --> 00:39:41,700
Joten aion mennä eteenpäin ja
välittömästi palautettava 0.

913
00:39:41,700 --> 00:39:45,920
Se vain ei ole mitään järkeä lisätä jopa kaikki
numeroita välillä 1 ja m, jos m

914
00:39:45,920 --> 00:39:48,470
itse 0 tai negatiivinen.

915
00:39:48,470 --> 00:39:50,900
>> Ja sitten aion mennä eteenpäin
ja tehdä tämän hyvin iteratiivisesti.

916
00:39:50,900 --> 00:39:53,090
Aion tehdä tällaista vanhan koulukunnan,
ja aion mennä eteenpäin

917
00:39:53,090 --> 00:39:57,150
ja sanoa, että aion
julistaa summa on 0.

918
00:39:57,150 --> 00:39:59,630
Sitten aion olla
varten silmukka int -

919
00:39:59,630 --> 00:40:02,820
ja anna minun tehdä se vastaamaan meidän
jakelu-koodi, joten sinulla on kopio

920
00:40:02,820 --> 00:40:07,500
kotona. int i saa 1 asti
i on pienempi tai yhtä suuri kuin m.

921
00:40:07,500 --> 00:40:09,430
i plus plus.

922
00:40:09,430 --> 00:40:11,430
Ja sitten sisällä tämän silmukan -

923
00:40:11,430 --> 00:40:12,440
olemme melkein perillä -

924
00:40:12,440 --> 00:40:15,810
summa saa summan plus 1.

925
00:40:15,810 --> 00:40:17,670
Ja sitten aion palata summa.

926
00:40:17,670 --> 00:40:19,420
>> Tein nopeasti,
melko tosin.

927
00:40:19,420 --> 00:40:22,775
Mutta jälleen kerran, päätehtävä on melko
suoraviivainen perustuva koodi olemme

928
00:40:22,775 --> 00:40:23,190
kirjoitettu tähän mennessä.

929
00:40:23,190 --> 00:40:25,610
Käyttää kaksoislenkin saada positiivista
int käyttäjältä.

930
00:40:25,610 --> 00:40:29,870
Sitten tapahtui, että int uusi toiminto
kutsutaan sigma, kutsuen sitä taas, n.

931
00:40:29,870 --> 00:40:33,100
Ja minä tallentaa palauttaa arvo, vastaus
alkaen musta laatikko hetkellä

932
00:40:33,100 --> 00:40:35,460
tunnettu sigma, muuttujaan
nimeltään vastaus.

933
00:40:35,460 --> 00:40:36,580
Sitten voin tulostaa sen.

934
00:40:36,580 --> 00:40:39,090
>> Jos me nyt jatkaa tarinaa,
miten sigma toteutetaan?

935
00:40:39,090 --> 00:40:40,840
Ehdotan toteuttaa seuraavasti.

936
00:40:40,840 --> 00:40:43,560
Ensin hieman virheentarkistava
varmistaa, että käyttäjä ei ole

937
00:40:43,560 --> 00:40:46,480
Messing minun kanssani ja kulkee
joitakin negatiivisia tai 0-arvo.

938
00:40:46,480 --> 00:40:49,710
Sitten Julistan muuttuja nimeltä
Yhteenvetona ja aseta se 0.

939
00:40:49,710 --> 00:40:55,910
>> Ja nyt alkaa siirtyä i vastaa
1 aina enintään m,

940
00:40:55,910 --> 00:41:00,130
koska haluan sisällyttää kaikki
numerot yhdestä kautta m, mukaan lukien.

941
00:41:00,130 --> 00:41:04,350
Ja sisällä tämä silmukka, en vain
summa saa mitä se on nyt, plus

942
00:41:04,350 --> 00:41:08,900
arvo i.

943
00:41:08,900 --> 00:41:10,370
Plus arvo i.

944
00:41:10,370 --> 00:41:14,090
>> Sivuhuomautuksena, jos et ole nähnyt tätä
ennen, on joitakin syntaktisia sokeria

945
00:41:14,090 --> 00:41:14,870
tällä linjalla.

946
00:41:14,870 --> 00:41:21,120
Voin kirjoittaa tätä plus vastaa i,
vain säästää itseäni muutamalla näppäimen painalluksella

947
00:41:21,120 --> 00:41:22,570
ja näyttää hieman viileämpi.

948
00:41:22,570 --> 00:41:23,140
Mutta siinä kaikki.

949
00:41:23,140 --> 00:41:24,660
Se on toiminnallisesti sama asia.

950
00:41:24,660 --> 00:41:26,710
>> Valitettavasti tämä koodi n
aio laatia vielä.

951
00:41:26,710 --> 00:41:31,600
Jos juoksen tehdä sigma 0, miten am
Olen menossa huusin?

952
00:41:31,600 --> 00:41:33,473
Mitä se aikoo pidä?

953
00:41:33,473 --> 00:41:35,740
>> Yleisö: [kuultavissa].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Joo, en julistaa
toiminto ylös, eikö?

955
00:41:37,800 --> 00:41:40,590
C on typerää, että se on omiaan
tekee mitä kerrot sen tehdä, ja sinun

956
00:41:40,590 --> 00:41:41,880
on tehtävä se tässä järjestyksessä.

957
00:41:41,880 --> 00:41:45,910
Joten jos osuin Anna tähän, aion
saada varoituksen sigma implisiittinen

958
00:41:45,910 --> 00:41:46,860
ilmoitus.

959
00:41:46,860 --> 00:41:48,120
>> Voi, ei ole ongelma.

960
00:41:48,120 --> 00:41:50,370
En voi mennä ylös, ja voin
sanoa, okei, odota hetki.

961
00:41:50,370 --> 00:41:54,240
Sigma on funktio, joka palauttaa
int ja se odottaa

962
00:41:54,240 --> 00:41:56,620
int syötteenä, puolipiste.

963
00:41:56,620 --> 00:41:59,550
Tai voisin laittaa koko toiminto
Edellä tärkein, mutta yleensä olin

964
00:41:59,550 --> 00:42:02,260
Suosittelen vastaan, että koska se on
kiva aina tärkein yläreunassa niin

965
00:42:02,260 --> 00:42:06,310
voit sukeltaa suoraan ja tietää, mitä
Ohjelma tekee lukemalla tärkein ensin.

966
00:42:06,310 --> 00:42:07,930
>> Joten nyt haluan tyhjentää näytön.

967
00:42:07,930 --> 00:42:09,330
Remake sigma 0.

968
00:42:09,330 --> 00:42:10,340
Kaikki näyttää tarkistaa.

969
00:42:10,340 --> 00:42:11,970
Saanen ajaa sigma 0.

970
00:42:11,970 --> 00:42:12,770
Positiivinen muun.

971
00:42:12,770 --> 00:42:15,580
Annan sen numeron
3. pitää se yksinkertainen.

972
00:42:15,580 --> 00:42:18,710
Niin, että pitäisi antaa minulle 3
plus 2 plus 1, niin 6.

973
00:42:18,710 --> 00:42:20,750
Anna, ja olen todellakin saat 6.

974
00:42:20,750 --> 00:42:21,820
>> Voin tehdä jotain suurempaa -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Aivan kuten tangentti, aion tehdä
jotain naurettavaa kuin todella iso

977
00:42:27,690 --> 00:42:30,375
numero, Oh, joka todella toiminut -

978
00:42:30,375 --> 00:42:31,600
eh, en usko, että on oikeassa.

979
00:42:31,600 --> 00:42:32,810
Katsotaanpa.

980
00:42:32,810 --> 00:42:34,060
Katsotaanpa todella sotkea sitä.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Se on ongelma.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Mitä on tekeillä?

985
00:42:44,970 --> 00:42:46,050
Koodia ei ole niin paha.

986
00:42:46,050 --> 00:42:48,470
Se on edelleen lineaarinen.

987
00:42:48,470 --> 00:42:50,810
Vihellys hyvä vaikutus, vaikka.

988
00:42:50,810 --> 00:42:52,060
Mitä on tekeillä?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Ole varma, jos olen kuullut sen.

991
00:42:55,620 --> 00:42:57,620
Joten se kääntyy pois - ja
tämä on niin syrjään.

992
00:42:57,620 --> 00:42:59,400
Tämä ei ole ydin
Ajatus rekursio.

993
00:42:59,400 --> 00:43:02,480
On käynyt ilmi, koska yritän
edustavat niin iso numero, useimmat

994
00:43:02,480 --> 00:43:06,980
todennäköisesti se tulkitaan väärin
by C ole positiivinen luku,

995
00:43:06,980 --> 00:43:09,980
mutta negatiivinen luku.

996
00:43:09,980 --> 00:43:12,690
>> Emme ole puhuneet tästä, mutta se
Osoittautuu olemassa negatiivisia lukuja

997
00:43:12,690 --> 00:43:14,210
maailman lisäksi
positiiviseen numeroita.

998
00:43:14,210 --> 00:43:16,290
Ja keinoja, joilla voit
edustavat negatiivinen luku

999
00:43:16,290 --> 00:43:19,530
pohjimmiltaan on, käytät yhden
erityisen vähän osoittamaan

1000
00:43:19,530 --> 00:43:20,400
ylijäämäisenä negatiivinen.

1001
00:43:20,400 --> 00:43:22,950
Se on hieman monimutkaisempi kuin, että
mutta se perusajatus.

1002
00:43:22,950 --> 00:43:26,740
>> Joten valitettavasti jos C on hämmentävä yksi
näistä bittejä todella tarkoittaa,

1003
00:43:26,740 --> 00:43:30,790
Voi, tämä on negatiivinen luku, minun loop
tässä, esimerkiksi, on itse asiassa koskaan

1004
00:43:30,790 --> 00:43:31,740
menossa lopettaa.

1005
00:43:31,740 --> 00:43:33,850
Joten jos olisin itse tulostaa jotain
uudelleen ja uudelleen, olisimme

1006
00:43:33,850 --> 00:43:34,650
nähdä paljon.

1007
00:43:34,650 --> 00:43:36,220
Mutta jälleen kerran, tämä on lisäksi kohta.

1008
00:43:36,220 --> 00:43:38,590
Tämä on oikeastaan ​​vain eräänlainen
älyllinen uteliaisuus, että tulemme

1009
00:43:38,590 --> 00:43:39,550
takaisin lopulta.

1010
00:43:39,550 --> 00:43:43,400
Mutta nyt, tämä on oikea
täytäntöönpanon jos oletamme, että

1011
00:43:43,400 --> 00:43:45,970
Käyttäjä antaa ints
että mahtuvat ints.

1012
00:43:45,970 --> 00:43:49,370
>> Mutta väitän, että tätä koodia, rehellisesti,
voitaisiin tehdä paljon yksinkertaisemmin.

1013
00:43:49,370 --> 00:43:54,060
Jos tavoitteena käsillä on ottaa useita
kuten m ja lisätä jopa kaikki

1014
00:43:54,060 --> 00:43:59,510
numeroita sen ja 1 tai päinvastoin
välillä 1 ja se, Väitän

1015
00:43:59,510 --> 00:44:03,380
että voin lainata tätä ajatusta, jotka sulautuvat
lajitella oli, joka otti ongelman

1016
00:44:03,380 --> 00:44:05,660
Tämän koko ja jakamalla se
osaksi jotain pienempää.

1017
00:44:05,660 --> 00:44:09,875
Ehkä ei puoli, mutta pienempiä, mutta
edustavasti sama.

1018
00:44:09,875 --> 00:44:12,130
Sama idea, mutta pienempi ongelma.

1019
00:44:12,130 --> 00:44:15,470
>> Joten olen todella - haluan tallentaa tiedoston
kanssa eri versionumero.

1020
00:44:15,470 --> 00:44:17,670
Soitamme tämän version
1 sijasta 0.

1021
00:44:17,670 --> 00:44:20,790
Ja väitän, että voin itse
reimplement tämä tämäntyyppisiin

1022
00:44:20,790 --> 00:44:22,160
aistiharhoja tavalla.

1023
00:44:22,160 --> 00:44:23,710
>> Aion jättää osa sitä yksin.

1024
00:44:23,710 --> 00:44:27,710
Aion sanoa, jos m on vähemmän
kuin tai jopa yhtä suuri kuin 0 -

1025
00:44:27,710 --> 00:44:29,280
Olen vain olemaan hieman
enemmän anaali tällä kertaa

1026
00:44:29,280 --> 00:44:30,520
minun virheentarkistukset -

1027
00:44:30,520 --> 00:44:33,190
Aion mennä eteenpäin ja palata 0.

1028
00:44:33,190 --> 00:44:34,490
Tämä on mielivaltainen.

1029
00:44:34,490 --> 00:44:37,500
Olen vain yksinkertaisesti päättää, jos käyttäjä
antaa minulle negatiivinen luku, olen

1030
00:44:37,500 --> 00:44:41,490
palaavat 0, ja ne olisi pitänyt lukea
asiakirjat tarkemmin.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
huomaa, mitä aion tehdä.

1033
00:44:44,070 --> 00:44:49,260
Else Aion palata m plus -

1034
00:44:49,260 --> 00:44:51,010
mikä on sigma m?

1035
00:44:51,010 --> 00:44:56,710
No, sigma m plus m miinus 1,
plus m miinus 2, plus m miinus 3.

1036
00:44:56,710 --> 00:44:58,030
En halua kirjoittaa kaiken tuon pois.

1037
00:44:58,030 --> 00:44:59,120
Miksi en vain potkaista?

1038
00:44:59,120 --> 00:45:05,080
Rekursiivisesti kutsua itseäni hieman
pienempi ongelma, puolipiste,

1039
00:45:05,080 --> 00:45:06,840
ja lopettaa tältä päivältä?

1040
00:45:06,840 --> 00:45:07,040
>> Oikea?

1041
00:45:07,040 --> 00:45:10,980
Nyt täälläkin, saatat tuntea tai huolehtia
että tämä on loputon silmukka, että olen

1042
00:45:10,980 --> 00:45:15,450
asiakkuutta, jolloin olen täytäntöönpanosta
sigma soittamalla sigma.

1043
00:45:15,450 --> 00:45:20,342
Mutta se on täysin OK, koska olen
ajattelin eteenpäin lisätty mitkä linjat?

1044
00:45:20,342 --> 00:45:22,600
>> Yleisö: [kuultavissa].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID MALAN: 23-26, jotka
on minun, jos kunnossa.

1046
00:45:25,430 --> 00:45:28,390
Koska mitä mukavaa noin
vähennyslaskua täällä, koska pidän

1047
00:45:28,390 --> 00:45:31,180
luovuttamalla sigma pienempiä ongelmia, pienempiä
ongelmia, pienempi - se ei ole

1048
00:45:31,180 --> 00:45:31,870
puolet pienempi.

1049
00:45:31,870 --> 00:45:34,380
Se on vain vauva pykälää pienempi,
mutta se on OK.

1050
00:45:34,380 --> 00:45:38,050
Koska lopulta, hoidamme
Matkalla alas 1 tai 0.

1051
00:45:38,050 --> 00:45:41,630
Ja kun osuimme 0, sigma ei ole
aikoo kutsua itseään enää.

1052
00:45:41,630 --> 00:45:43,590
Se tulee välittömästi palata 0.

1053
00:45:43,590 --> 00:45:47,960
>> Joten vaikutus, jos sellainen tuulen tämän
up mielessäsi, on lisätä m +

1054
00:45:47,960 --> 00:45:52,740
m miinus 1, plus m miinus 2, plus m miinus
3, plus piste, piste, piste, m miinus

1055
00:45:52,740 --> 00:45:57,820
m, lopulta antaa sinulle 0, ja
vaikutus on viime kädessä lisätä kaikkien

1056
00:45:57,820 --> 00:45:59,070
nämä asiat yhdessä.

1057
00:45:59,070 --> 00:46:02,380
Joten meillä ei ole, ja rekursio,
ratkaista ongelma, että me

1058
00:46:02,380 --> 00:46:03,470
ei ratkaista ennen.

1059
00:46:03,470 --> 00:46:06,840
Todellakin, versio 0 tämän ja jokainen
Ongelmana on tähän asti ollut ratkaistavissa

1060
00:46:06,840 --> 00:46:09,980
vain käyttämällä silmukoita tai kun
silmukoita tai vastaavia rakenteita.

1061
00:46:09,980 --> 00:46:13,150
>> Mutta rekursio, Luulen, antaa meille
erilainen tapa ajatella

1062
00:46:13,150 --> 00:46:17,010
ongelmia, jolloin jos voimme ottaa
ongelma, jakaa sitä jotain

1063
00:46:17,010 --> 00:46:22,340
suurehko jotain hieman
pienempi, Väitän, että voimme ratkaista sen

1064
00:46:22,340 --> 00:46:26,040
ehkä hieman tyylikkäästi kannalta
suunnittelu, vähemmän koodia,

1065
00:46:26,040 --> 00:46:30,980
ja ehkä jopa ratkaisemaan ongelmia, jotka
olla vaikeampaa, kuten tulemme lopulta

1066
00:46:30,980 --> 00:46:33,280
katso, ratkaista puhtaasti iteratiivisesti.

1067
00:46:33,280 --> 00:46:35,980
>> Mutta jännitysnäytelmä, että tein
halua lähteä meitä oli tämä.

1068
00:46:35,980 --> 00:46:40,720
Anna minun mennä eteenpäin ja avata
up tiedosto -

1069
00:46:40,720 --> 00:46:44,300
todella, anna minun mennä ja
tehdä tämän todella nopeasti.

1070
00:46:44,300 --> 00:46:46,875
Anna minun mennä eteenpäin ja ehdottaa
seuraavat.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Tämän päivän koodi on tämä tiedosto tästä.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Tämä yksi täällä, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Joten tämä on typerä pieni ohjelma, joka
Olen lyöty jopa joka väittää tehdä

1076
00:47:06,260 --> 00:47:06,940
seuraavat.

1077
00:47:06,940 --> 00:47:10,140
Main, se ilmoittaa ensin
int kutsutaan x ja määrittää sen

1078
00:47:10,140 --> 00:47:11,100
arvon 1.

1079
00:47:11,100 --> 00:47:13,520
Sitten se ilmoittaa, int y ja
määrittää sen arvo 2.

1080
00:47:13,520 --> 00:47:15,310
Sitten se tulostaa mitä x ja y on.

1081
00:47:15,310 --> 00:47:17,781
Sitten se sanoo, vaihtamalla, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Sitten se väittää vaatii toimia
nimeltään swap, ohimennen x ja

1083
00:47:21,670 --> 00:47:24,290
y, ajatus on, että toivottavasti
x ja y tulevat takaisin

1084
00:47:24,290 --> 00:47:25,620
eri, päinvastoin.

1085
00:47:25,620 --> 00:47:27,110
Sitten se väittää vaihdettu!

1086
00:47:27,110 --> 00:47:28,420
huutomerkki.

1087
00:47:28,420 --> 00:47:30,190
Sitten se tulostaa x ja y.

1088
00:47:30,190 --> 00:47:33,480
>> Mutta näyttää siltä, ​​että tämä hyvin
yksinkertainen esittelyä alas

1089
00:47:33,480 --> 00:47:35,570
täällä on todella buginen.

1090
00:47:35,570 --> 00:47:38,870
Vaikka olen julistamisesta väliaikainen
muuttuja ja tilapäisesti käyttöön vuonna

1091
00:47:38,870 --> 00:47:42,010
sitä, niin olen vaihtaminen mille
b: n arvo -

1092
00:47:42,010 --> 00:47:45,080
joka tuntuu kohtuullinen, koska olen
tallennettu kopio temp.

1093
00:47:45,080 --> 00:47:48,410
Sitten voin päivittää b yhdenvertaiseen
mikä oli temp.

1094
00:47:48,410 --> 00:47:51,610
Tällainen kuori peli liikkuvat
osaksi b ja b osaksi käyttämällä tätä

1095
00:47:51,610 --> 00:47:54,360
keski-mies nimeltä temp tuntuu
täysin järkevää.

1096
00:47:54,360 --> 00:47:57,270
>> Mutta väitän, että kun juoksen tämän
koodi, kuten minä teen nyt -

1097
00:47:57,270 --> 00:47:59,490
anna minun mennä eteenpäin ja liitä se täällä.

1098
00:47:59,490 --> 00:48:01,995
Soitan tämän noswap.c.

1099
00:48:01,995 --> 00:48:05,630
Ja kuten nimestä voi päätellä, tämä ei ole
olemaan oikea ohjelma.

1100
00:48:05,630 --> 00:48:09,460
Tee noswap. / Ei swap.

1101
00:48:09,460 --> 00:48:12,110
x 1, y on 2, vaihtamalla, vaihdoin.

1102
00:48:12,110 --> 00:48:14,220
x on 1, y on 2.

1103
00:48:14,220 --> 00:48:16,920
Tämä on täysin väärä, vaikka
vaikka tämä vaikuttaa täysin

1104
00:48:16,920 --> 00:48:17,730
järkevää minulle.

1105
00:48:17,730 --> 00:48:21,330
Ja siellä on syy, mutta emme ole
aikoo paljastaa syy vielä.

1106
00:48:21,330 --> 00:48:24,610
>> Nyt toinen jännitysnäytelmä halusin
jätä sinua on tämä,

1107
00:48:24,610 --> 00:48:27,120
ilmoitus tapaisena kuponkikoodeista.

1108
00:48:27,120 --> 00:48:31,590
Innovaatioiden myöhään päivää tänä vuonna
on herättänyt ei-triviaali määrä

1109
00:48:31,590 --> 00:48:33,830
kysymyksiä, jotka oli
Tarkoituksemme ei ole.

1110
00:48:33,830 --> 00:48:36,590
Tarkoituksena näistä kuponkikoodeista,
jolloin jos teet osa ongelmaa

1111
00:48:36,590 --> 00:48:39,850
asettaa aikaisin, mikä saada ylimääräinen päivä,
oli todella auttaa teitä auttaa

1112
00:48:39,850 --> 00:48:42,420
itse aloittaa aikaisin, sort
ja palkitsemalla sinua.

1113
00:48:42,420 --> 00:48:44,880
Auttaa meitä jakamaan kuormaa poikki
virka paremmin niin, että

1114
00:48:44,880 --> 00:48:45,740
se on eräänlainen win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Valitettavasti luulen ohjeet
ei ole ollut tähän mennessä hyvin kirkas, niin

1116
00:48:48,860 --> 00:48:52,230
Menin takaisin tänä viikonloppuna ja päivitetään
spec suurempi, rohkeampi teksti

1117
00:48:52,230 --> 00:48:53,600
selittää luoteja kuin nämä.

1118
00:48:53,600 --> 00:48:56,900
Ja vain sanoa sen avoimempi, jonka
Oletuksena ongelma sarjaa johtuvat torstai

1119
00:48:56,900 --> 00:48:58,400
keskipäivällä, per oppimäärän.

1120
00:48:58,400 --> 00:49:02,030
Jos aloitat varhain, viimeistely osa
ongelma asettamat keskiviikkona klo 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, osa, joka liittyy kuponki
koodi, ajatus on, että voit laajentaa

1122
00:49:05,170 --> 00:49:07,710
teidän määräaika
P asettaa vasta perjantaina.

1123
00:49:07,710 --> 00:49:10,890
Eli hieman pois pieni osa P
asettaa siihen, mitä on tyypillisesti

1124
00:49:10,890 --> 00:49:13,200
suurempi ongelma, ja ostat
itse ylimääräinen päivä.

1125
00:49:13,200 --> 00:49:15,190
Jälleen, se saa sinut ajattelemaan
Harjoitus, saa sinut

1126
00:49:15,190 --> 00:49:16,380
virka nopeammin.

1127
00:49:16,380 --> 00:49:20,670
Mutta kuponkikoodi ongelma on edelleen
tarvitaan, vaikka et lähetä se.

1128
00:49:20,670 --> 00:49:23,340
>> Mutta enemmän pakottavan on tämä.

1129
00:49:23,340 --> 00:49:26,520
(Stage Whisper) Ja ne ihmiset lähtevät
alussa tulet katumaan sitä.

1130
00:49:26,520 --> 00:49:28,620
Koska ovat seudullamme parvekkeella.

1131
00:49:28,620 --> 00:49:32,510
Pahoittelen jo etukäteen seudullamme
parveke syistä, jotka on

1132
00:49:32,510 --> 00:49:33,920
tyhjentää vain hetken.

1133
00:49:33,920 --> 00:49:37,050
>> Joten olemme onnekkaita olla yksi
CS50: n entinen johtaja opetus Fellows

1134
00:49:37,050 --> 00:49:39,302
yritys nimeltä dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
He ovat hyvin anteliaasti lahjoitti
kuponkikoodi täällä näin paljon tilaa,

1136
00:49:45,500 --> 00:49:48,180
joka on ylös
tavallisesti 2 gigatavua.

1137
00:49:48,180 --> 00:49:51,740
Joten mitä ajattelin tekisimme tästä
Viimeinen huomautus on tehdä vähän kylkiäinen,

1138
00:49:51,740 --> 00:49:55,380
jolloin vain hetki, me paljastaa
voittaja ja joka on kuponki

1139
00:49:55,380 --> 00:49:57,980
koodia, jota voi sitten mennä heidän
verkkosivuilla, kirjoita se, ja voila, saada

1140
00:49:57,980 --> 00:50:01,370
paljon enemmän Dropbox tilaa
laite ja henkilökohtaiset tiedostot.

1141
00:50:01,370 --> 00:50:05,690
>> Ja ensimmäinen, joka haluaa osallistua
tässä piirustuksessa?

1142
00:50:05,690 --> 00:50:09,630
OK, nyt joka tekee siitä entistä hauskempaa.

1143
00:50:09,630 --> 00:50:14,010
Henkilö, joka saa tämän 25 gigatavun
kuponkikoodi - joka on kaukana

1144
00:50:14,010 --> 00:50:16,150
enemmän pakottavia kuin myöhään
päivän ajan, kenties -

1145
00:50:16,150 --> 00:50:20,620
on se, joka istuu päälle
istuinosan alla, joka on

1146
00:50:20,620 --> 00:50:21,620
että kuponkikoodi.

1147
00:50:21,620 --> 00:50:23,480
Voit nyt katsoa alla
oman istuintyynyn.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEOTOISTOSTA]

1150
00:50:29,680 --> 00:50:31,620
>> -Yksi, kaksi, kolme.

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>> -Saat auton!

1153
00:50:35,985 --> 00:50:36,670
Saat auton!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID MALAN: Tulemme näkemään
keskiviikkona.

1155
00:50:37,970 --> 00:50:38,904
>> -Saat auton!

1156
00:50:38,904 --> 00:50:39,371
Saat auton!

1157
00:50:39,371 --> 00:50:40,305
Saat auton!

1158
00:50:40,305 --> 00:50:41,706
Saat auton!

1159
00:50:41,706 --> 00:50:43,107
Saat auton!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID MALAN: Parveke ihmiset, tulevat
tänne eteen,

1161
00:50:45,530 --> 00:50:46,866
jossa meillä on extrat.

1162
00:50:46,866 --> 00:50:50,282
>> -Jokainen saa auton!

1163
00:50:50,282 --> 00:50:52,234
Jokainen saa auton!

1164
00:50:52,234 --> 00:50:52,722
>> [END VIDEOTOISTOSTA]

1165
00:50:52,722 --> 00:50:54,590
>> Kertoja: Seuraavassa CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Jestas Gosh Gosh Gosh
Gosh Gosh Gosh Gosh Gosh Gosh -

1167
00:51:00,374 --> 00:51:02,106
>> [Ukelele PLAYS]