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

2
00:00:11,270 --> 00:00:14,910
>> Puhuja: Okei, tämä on CS50.

3
00:00:14,910 --> 00:00:19,020
Tämä on viikon lopussa kolme, ja jos
et ole hyödyntäneet jo,

4
00:00:19,020 --> 00:00:21,790
tietää, että siellä on lounas
perjantaina kuten tavallista, jos

5
00:00:21,790 --> 00:00:25,430
voit nauttia hyvä keskustelu
ja ruokaa Fire and Ice

6
00:00:25,430 --> 00:00:27,980
joidenkin CS50: n
henkilöstö ja luokkatoverit.

7
00:00:27,980 --> 00:00:30,170
Suunnata tätä URL täällä.

8
00:00:30,170 --> 00:00:33,420
>> Nyt ehkä muistatte, tai et
saattaa pian olla perehtynyt,

9
00:00:33,420 --> 00:00:35,970
näitä asioita täällä, mikä
annetaan ulos lopussa

10
00:00:35,970 --> 00:00:37,850
lukukauden monta luokkaa.

11
00:00:37,850 --> 00:00:40,870
Ns tentti sininen kirjoja, joissa
kirjoitat vastauksia tentit.

12
00:00:40,870 --> 00:00:44,240
Nyt minulla on täällä 26 tällaista
sininen kirjoja, kummallakin niistä

13
00:00:44,240 --> 00:00:47,580
on kirjoitettu nimi, Z. Ja
todellakin nimet ovat niin yksinkertaista,

14
00:00:47,580 --> 00:00:50,490
Z. Ja yksi
tavoitteet käsillä tänään

15
00:00:50,490 --> 00:00:53,910
tulee olemaan jatkossakin mitä
aloitimme maanantaina, joka ei ole

16
00:00:53,910 --> 00:00:57,830
niin paljon katsot koodin, mutta oikeastaan
pohtivat ja ongelmanratkaisuun.

17
00:00:57,830 --> 00:01:00,170
Yksi tavoitteista ja
lupaukset Kurssin

18
00:01:00,170 --> 00:01:02,985
on opettaa sinut ajattelemaan enemmän
huolellisesti, enemmän suunnitelmallisesti,

19
00:01:02,985 --> 00:01:05,400
ja ratkaisemaan ongelmia tehokkaammin.

20
00:01:05,400 --> 00:01:09,526
Ja todellakin, voimme tehdä, että todella
ilman edes kosketa riviä koodia.

21
00:01:09,526 --> 00:01:12,150
Joten minulla on pari norsuja
täällä tänään, oranssi ja sininen,

22
00:01:12,150 --> 00:01:15,780
jos voisimme saada yksi vapaaehtoinen,
ehkä alkaen kauemmaksi kuin normaalisti.

23
00:01:15,780 --> 00:01:18,070
Entä tuolla, tule alas.

24
00:01:18,070 --> 00:01:24,180
Päämääränä tulee olla
auttaa sekä hallinnoida tätä tentti täällä.

25
00:01:24,180 --> 00:01:24,935
Mikä sinun nimesi on?

26
00:01:24,935 --> 00:01:25,768
>> Yleisö: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
Puhuja: Mary Beth, tule ylös.

28
00:01:27,560 --> 00:01:29,560
Otan mikrofonin täällä sinua varten.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Hauska tavata.

31
00:01:32,880 --> 00:01:34,005
>> Yleisö: Hauska tavata.

32
00:01:34,005 --> 00:01:36,790
Puhuja: Okei, joten minulla on
tässä sininen kirjoja Z,

33
00:01:36,790 --> 00:01:41,680
ja aion teeskennellä, että
Minulla on yksi opiskelijoista,

34
00:01:41,680 --> 00:01:45,770
ja he tulevat jokseenkin satunnaisesti
lopussa kolmen tunnin tentti lohko,

35
00:01:45,770 --> 00:01:49,400
joten he päätyvät joidenkin
semi-satunnaisessa järjestyksessä näin.

36
00:01:49,400 --> 00:01:54,510
Nyt työsi vain hetki on menossa
to olet-- tämä on todella miten he saavat

37
00:01:54,510 --> 00:01:56,820
kääntyi lopussa
luokka, todennäköisimmin.

38
00:01:56,820 --> 00:02:01,120
Työsi nyt tulee olemaan varsin
yksinkertaisesti, lajitella nämä siniset kirjat meille

39
00:02:01,120 --> 00:02:05,220
alkaen Z.

40
00:02:05,220 --> 00:02:08,400
>> Yleisö: Voi, tämä on
vie ikuisesti.

41
00:02:08,400 --> 00:02:13,747
>> Puhuja: Ja me seuraamme
kun teette tämän, ei paineita.

42
00:02:13,747 --> 00:02:15,330
Yleisö: Ei mitään painetta tai jotain.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> Puhuja: Ja hauskaa,
Katsotaanpa sietää ajastin.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> Yleisö: niin hauskaa, niin hauskaa.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> Puhuja: Voin pitää mikrofoni sinulle.

49
00:02:38,574 --> 00:02:40,240
Okei, olemme juuri kaksinkertaistaneet nopeutta.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Joten sillä välin, haluan aiheuttaa mitä
olemaan kysymys Mary Beth

52
00:02:49,060 --> 00:02:51,540
on mitä hän tekee, miten on
hän menee noin ratkaista tämä?

53
00:02:51,540 --> 00:02:54,040
Ja itse asiassa, sinulla ei ehkä ole
koskaan ajatellut jotain

54
00:02:54,040 --> 00:02:57,440
niin yksinkertainen kuin noudettaessa
jopa 26 kirjoja, kuten tämä,

55
00:02:57,440 --> 00:02:59,350
joka ei ole luonnollinen
tilaamalla niitä.

56
00:02:59,350 --> 00:03:01,335
Mikä on prosessi
joita käytät?

57
00:03:01,335 --> 00:03:03,770
Onko se melko sattumanvaraisesti vain
poiminta ensimmäinen näet

58
00:03:03,770 --> 00:03:05,250
ja laitat sen paikoilleen?

59
00:03:05,250 --> 00:03:09,680
Oletteko ensin liikuttaa käsiäsi ympäri
HAKU sitten etsivät B?

60
00:03:09,680 --> 00:03:11,722
Oletteko katsomaan
pari vierekkäin

61
00:03:11,722 --> 00:03:14,680
ja vain sanoa, hetkinen, tämä
ei ole oikein, ja sitten vaihtaa tilauksen?

62
00:03:14,680 --> 00:03:16,960
Näimme jo maanantaina
että on olemassa useita tapoja

63
00:03:16,960 --> 00:03:22,140
jossa voimme tehdä tämän, ja
todellakin kuten olemme lähellä loppua täällä,

64
00:03:22,140 --> 00:03:26,360
Ottaisin merkille ehkä
mitä Mary Beth tekee.

65
00:03:26,360 --> 00:03:30,040
Meillä on muutama paalut näyttää siltä,
isompi, kolmen pienemmän.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> Yleisö: Käsken heitä
kun löydän kaksi kirjainta

68
00:03:36,415 --> 00:03:39,540
että tiedän ovat yhdessä järjestyksessä,
Laitoin ne yhteen niin, että en

69
00:03:39,540 --> 00:03:42,915
tarvitse murehtia pitää
Seuraa koko rivi kirjoja.

70
00:03:42,915 --> 00:03:45,706
Se on vain, oi, on ensimmäinen,
Minulla tämä pino täällä.

71
00:03:45,706 --> 00:03:47,580
Puhuja: Niin, melkein kuin
palapelin palaset

72
00:03:47,580 --> 00:03:49,860
on oikeus muodon
sovittaa toisiinsa.

73
00:03:49,860 --> 00:03:51,026
Yleisö: Aika paljon, joo.

74
00:03:51,026 --> 00:03:55,320
Puhuja: OK, erinomainen.

75
00:03:55,320 --> 00:03:59,850
Ja nyt jokainen näistä
paalut on oletettavasti lajitellaan?

76
00:03:59,850 --> 00:04:00,990
>> Yleisö: Joo.

77
00:04:00,990 --> 00:04:09,900
>> Puhuja: Okei, Z. Kaikki
oikea, onnittelut, teit sen.

78
00:04:09,900 --> 00:04:11,461
Sinulla on valintasi.

79
00:04:11,461 --> 00:04:11,960
Sininen?

80
00:04:11,960 --> 00:04:13,530
Okei, kiitos siitä.

81
00:04:13,530 --> 00:04:16,679
Joten Mary Beth ei ehdottamaan
mitä hänen lähestymistapa oli,

82
00:04:16,679 --> 00:04:19,720
mutta mikä on toinen lähestymistapa miten
voisi mennä noin lajittelu näitä asioita?

83
00:04:19,720 --> 00:04:21,130
Mitä sinä olisit tehnyt?

84
00:04:21,130 --> 00:04:24,060
Ennätys maalia olisi ollut
yhden minuutin ja 50 tai niin sekuntia,

85
00:04:24,060 --> 00:04:26,039
plus ne unohdin laskea.

86
00:04:26,039 --> 00:04:27,080
Mitä sinä olisit tehnyt?

87
00:04:27,080 --> 00:04:27,579
Joo?

88
00:04:27,579 --> 00:04:28,735
Yleisö: Ota pino.

89
00:04:28,735 --> 00:04:29,776
Aloittaa alusta.

90
00:04:29,776 --> 00:04:32,284
Tarkista paperit.

91
00:04:32,284 --> 00:04:36,586
Ja jos alkuun yksi on korkeampi
kuin, ehkä he ovat,

92
00:04:36,586 --> 00:04:38,980
alempi on
korkeampi, sitten vaihtaa niitä.

93
00:04:38,980 --> 00:04:41,300
>> Puhuja: OK, niin alkaa
ylhäältä ja alhaalta,

94
00:04:41,300 --> 00:04:43,716
ja sitten työ tiesi
sisäänpäin niin, vaihtamalla niitä?

95
00:04:43,716 --> 00:04:46,580
OK, joten vähän samanlainen
hengeltään kupla lajitella,

96
00:04:46,580 --> 00:04:49,160
mutta valinta ääripäitä
ei vierekkäiset.

97
00:04:49,160 --> 00:04:52,080
Mutta lyhyt se on, että siellä on
varmasti joukko eri tavoin

98
00:04:52,080 --> 00:04:54,210
voisimme tehdä tämän, ja
rehellisesti, mielestäni sinun eräänlainen

99
00:04:54,210 --> 00:04:55,700
hyväksyi pari lähestymistapoja, eikö?

100
00:04:55,700 --> 00:05:00,567
Teit tavallaan neljä lajitellun paalut, ja
sitten käytännössä sulautettiin yhteen.

101
00:05:00,567 --> 00:05:02,650
Ja se, daresay, toinen
tekniikka kokonaan.

102
00:05:02,650 --> 00:05:06,950
Et käsittele se yksi iso kasa,
voit jakaa ongelman neljään neloset,

103
00:05:06,950 --> 00:05:09,820
jos haluatte, ja sitten jotenkin
yhdistettiin ne lopulta.

104
00:05:09,820 --> 00:05:13,410
>> Joten harkita, lopulta,
Miten muuten voisimme tehdä tämän.

105
00:05:13,410 --> 00:05:15,860
Me virallistettiin käsite
kupla lajitella viime kerralla,

106
00:05:15,860 --> 00:05:18,780
ja kupla lajitella takaisinkutsu
algoritmi että me visualisoidaan

107
00:05:18,780 --> 00:05:22,640
kahdeksan oppilastoverisi tänne,
näennäisen satunnaisesti lajitellaan ensin.

108
00:05:22,640 --> 00:05:26,110
Jolloin päätimme pairwise, jos
kaksi tekijää ovat epäkunnossa,

109
00:05:26,110 --> 00:05:26,950
yksinkertaisesti vaihtaa niitä.

110
00:05:26,950 --> 00:05:28,930
Joten neljä ja kaksi
ilmeisesti epäkunnossa,

111
00:05:28,930 --> 00:05:31,080
joten nämä kaksi luokkatoverit
kytketty kantoja.

112
00:05:31,080 --> 00:05:35,390
Ja sitten me toistettiin neljä ja kuusi,
sitten kuusi ja kahdeksan, on jokaisen iteraation,

113
00:05:35,390 --> 00:05:36,980
siirtymässä oikealle.

114
00:05:36,980 --> 00:05:42,590
>> Joten annettiin kahdeksan ihmistä, kuinka monta pairwise
vertailuja tein kävellessä alkaen

115
00:05:42,590 --> 00:05:45,220
vasemmalta oikealle yksi tällainen iteraatio?

116
00:05:45,220 --> 00:05:48,410
Kuinka monta vertailuja?

117
00:05:48,410 --> 00:05:49,197
Seitsemän, eikö?

118
00:05:49,197 --> 00:05:51,405
Koska jos siellä on kahdeksan
ihmisiä, mutta sinulla on pari

119
00:05:51,405 --> 00:05:53,880
heitä ja olet liikkeessä
yksi hop oikealle,

120
00:05:53,880 --> 00:05:56,060
et aio olla kahdeksan
vertailuja, koska et voi verrata

121
00:05:56,060 --> 00:05:59,226
elementti itseään vastaan, tai se olisi
vain olla turhaa, joten sinulla on seitsemän.

122
00:05:59,226 --> 00:06:01,290
Tai yleisemmin, jos
meillä n ihmisiä, me

123
00:06:01,290 --> 00:06:04,300
tehdä n miinus 1 vertailut
kupla lajitella.

124
00:06:04,300 --> 00:06:08,150
>> Joten Tarkastellaan nyt miten hyvä tai
paha kupla lajitella todellisuudessa oli, ja yritä

125
00:06:08,150 --> 00:06:13,570
antaa itsellemme sanaston
josta kritiikki algoritmeja näin,

126
00:06:13,570 --> 00:06:14,430
ja pian omamme.

127
00:06:14,430 --> 00:06:16,970
Joten ensimmäinen läpi
kupla lajitella, ensimmäisen kerran

128
00:06:16,970 --> 00:06:20,909
Kävelin vasemmalta oikealle poikki
vaiheessa, vei minut n miinus 1 vertailuja.

129
00:06:20,909 --> 00:06:22,950
Ja se tulee olemaan minun
mittayksikkö, eikö?

130
00:06:22,950 --> 00:06:26,170
Olin sellainen puhuminen ja kiertelevä,
jonkin verran nopea, hieman hidas,

131
00:06:26,170 --> 00:06:29,300
joten laskemalla minun monta sekuntia
ei ole erityisen vahva,

132
00:06:29,300 --> 00:06:32,260
mutta lukumäärää laskettaessa
toiminnot, jotka tein maanantaina,

133
00:06:32,260 --> 00:06:35,900
vertaamalla kahta ihmistä, joka tuntuu
kuten mukava mittayksikkö.

134
00:06:35,900 --> 00:06:40,980
>> Joten n miinus 1 askeleen ensimmäistä kertaa,
mutta mitä sitten sen jälkeen tapahtui?

135
00:06:40,980 --> 00:06:46,610
Mikä on yksi ylösalaisin yhden pass
kautta muuten lajittelemattomat lista?

136
00:06:46,610 --> 00:06:49,840
Mitä voit kertoa elementti
joka oli aina siellä?

137
00:06:49,840 --> 00:06:51,300
Joo?

138
00:06:51,300 --> 00:06:52,870
Se oli suurin tekijä, eikö?

139
00:06:52,870 --> 00:06:55,710
Numero kahdeksan, vaikka hän
talla, joka kerta kun

140
00:06:55,710 --> 00:06:57,860
verrannut häntä vastaan
naapuri, hän piti

141
00:06:57,860 --> 00:07:00,480
kuplii oikealle
laidassa luettelon.

142
00:07:00,480 --> 00:07:02,710
Ja todellakin, sinne
algoritmi on saanut nimensä.

143
00:07:02,710 --> 00:07:07,630
>> Nyt tämän logiikan, kuinka monta vertailut
tarvitseeko minun tehdä siitä toisen kerran

144
00:07:07,630 --> 00:07:09,800
Teen joka syötön vasemmalta oikealle?

145
00:07:09,800 --> 00:07:10,730
n miinus 2, eikö?

146
00:07:10,730 --> 00:07:14,297
Se olisi vain tuhlaa aikaani, jos en
pitää vertaamalla kahdeksan henkilöä vastaan

147
00:07:14,297 --> 00:07:16,630
muuten koska tiedämme jo
Hän oli oikeassa paikassa.

148
00:07:16,630 --> 00:07:19,760
Niin, että vähän
optimointi, joten seuraava pass

149
00:07:19,760 --> 00:07:23,899
tulee olemaan plus n miinus kaksi vaihetta,
jossa n on määrä ihmisiä.

150
00:07:23,899 --> 00:07:26,940
Nyt voit sellaista ekstrapoloida, vaikka
jos et ole tietojenkäsittelytieteessä,

151
00:07:26,940 --> 00:07:27,680
miten tämä päättyy.

152
00:07:27,680 --> 00:07:31,259
Lopussa tämän algoritmin, oletettavasti
sinulla vain yksi vertailu jäljellä.

153
00:07:31,259 --> 00:07:33,800
Sinun täytyy tavallaan korjata
alussa luettelon tapauksessa kaksi

154
00:07:33,800 --> 00:07:36,540
ja yksi on epäkunnossa
ja sen pitäisi olla yksi ja kaksi,

155
00:07:36,540 --> 00:07:40,330
joten tämä on pohjassa osoitteessa
plus 1 lopullinen vertailu.

156
00:07:40,330 --> 00:07:44,500
>> Nyt piste, piste, piste sellainen aallot sen
kädet joitakin mehukkaampi yksityiskohtia,

157
00:07:44,500 --> 00:07:46,452
mutta haluan vain mennä eteenpäin ja yksinkertaistaa.

158
00:07:46,452 --> 00:07:48,660
Jos muistatte korkea
koulu, rehellisesti, monet teistä

159
00:07:48,660 --> 00:07:50,340
oli matematiikan kirjoja, jotka oli
hieman lunttilappua

160
00:07:50,340 --> 00:07:52,550
kannessa tai
takakansi että näytin sinulle

161
00:07:52,550 --> 00:07:56,400
mikä sarja summations kuten
tämä lopulta lisätään enintään.

162
00:07:56,400 --> 00:07:59,600
Yleisessä tapauksessa, jos sinulla on
muuttuja kuten n, ja todellakin tämä,

163
00:07:59,600 --> 00:08:01,634
jos katsoit
vanhan koulun matematiikan kirjan,

164
00:08:01,634 --> 00:08:04,050
voit nähdä, että tämä todella
lisää jopa tämän summan täällä,

165
00:08:04,050 --> 00:08:07,970
n kertaa n miinus 1 kaikki jaettuna 2.

166
00:08:07,970 --> 00:08:11,172
Joten nyt haluan vain säätää
tämä on totta, niin on uskonharppaus

167
00:08:11,172 --> 00:08:12,880
sitähän tämä kiteyttää
asti, ja voisimme

168
00:08:12,880 --> 00:08:14,341
todistaa, että yleisempi tapaus.

169
00:08:14,341 --> 00:08:15,590
Mutta nyt katsotaanpa laajentaa tätä.

170
00:08:15,590 --> 00:08:19,920
Joten kerrottava tämä pois, niin se on
n potenssiin miinus n, kaikki jaettuna 2.

171
00:08:19,920 --> 00:08:23,200
Se on todella n potenssiin,
jaettuna 2, miinus n yli 2,

172
00:08:23,200 --> 00:08:25,010
niin että kaikki kiva ja mielenkiintoinen.

173
00:08:25,010 --> 00:08:27,060
Mutta mitä tapahtuu, jos me
nyt plug-in arvo?

174
00:08:27,060 --> 00:08:29,724
Oletetaan En ole kahdeksan
ihmiset, mutta sanovat miljoonaa euroa.

175
00:08:29,724 --> 00:08:31,890
Ja miljoona vain siksi
se on aika iso määrä,

176
00:08:31,890 --> 00:08:34,039
katsotaanpa plug että ja katso mitä tapahtuu.

177
00:08:34,039 --> 00:08:39,039
Joten jos kytken miljoonaa tuohon kaava
Aion saada miljoona potenssiin,

178
00:08:39,039 --> 00:08:42,868
jaettuna 2, miinus
euroa, jaettuna 2.

179
00:08:42,868 --> 00:08:44,159
Mitä nyt se sujuu yhtä suureksi?

180
00:08:44,159 --> 00:08:47,354
Joten 500 miljardia, miinus 500000.

181
00:08:47,354 --> 00:08:49,270
Ja jos minä itse tehdä
että matematiikka ulos, että välineet

182
00:08:49,270 --> 00:08:53,920
että lajittelu miljoonaa
ihmiset kupla lajitella

183
00:08:53,920 --> 00:09:01,800
Ottaa minut 499999500000
vaiheet tai vertailuja varten

184
00:09:01,800 --> 00:09:02,900
me vain päättelemällä.

185
00:09:02,900 --> 00:09:06,860
>> Joka tuntuu melko hidas, mutta suoraan sanottuna
mittaamalla tietyn tulo

186
00:09:06,860 --> 00:09:09,160
näin, ei ole kovin kuvaava.

187
00:09:09,160 --> 00:09:14,050
Mutta tosiaan se tarkoittaa kuitenkin sitä, että n
saa suurempia, tämä algoritmi

188
00:09:14,050 --> 00:09:16,280
tavallaan tuntuu huonompi ja
pahempaa, tai todella

189
00:09:16,280 --> 00:09:20,450
alkaa tuntea kipua, joka
eksponenttilausekkeet, että n potenssiin,

190
00:09:20,450 --> 00:09:21,770
joka lisää jopa melko nopeasti.

191
00:09:21,770 --> 00:09:25,340
Ja näin yksityiskohtaisia ​​tietoja ei ole
menetetty ihmisiä, itse asiassa

192
00:09:25,340 --> 00:09:29,640
joitakin vuosia sitten tietty senaattori, joka oli
kampanjointi, istui haastatteluun

193
00:09:29,640 --> 00:09:32,180
Googlen Eric
Schmidt, toimitusjohtaja tuolloin,

194
00:09:32,180 --> 00:09:36,380
ja altistettiin kysymys
aivan kuten me tutkia tänään.

195
00:09:36,380 --> 00:09:38,468
Katsotaanpa katsomaan.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEOTOISTOSTA]

197
00:09:45,280 --> 00:09:48,560
>> -Senaattori, Olet täällä
Google, ja pidän

198
00:09:48,560 --> 00:09:53,382
ajatella puheenjohtajakauden
kuin työhaastattelu.

199
00:09:53,382 --> 00:09:56,434
Nyt on vaikea saada
työtä presidenttinä,

200
00:09:56,434 --> 00:09:58,100
ja olet menossa läpi jäykkyys nyt.

201
00:09:58,100 --> 00:10:01,860
On myös vaikea saada työpaikan Google.

202
00:10:01,860 --> 00:10:05,490
Meillä on kysymyksiä, ja me
kysy ehdokkaita kysymyksiä,

203
00:10:05,490 --> 00:10:09,770
ja tämä yksi on Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
What-- te olette mieltä olen
leikkiä, se on täällä.

205
00:10:14,760 --> 00:10:17,930
Mikä on tehokkain tapa
lajitella miljoonaa 32-bittisiä kokonaislukuja?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> Olen pahoillani, maybe--

209
00:10:25,200 --> 00:10:27,400
>> Ei, ei, ei.

210
00:10:27,400 --> 00:10:30,700
Mielestäni kupla lajitella
olisi väärä tie.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> Tule, jotka kertoivat hänelle tämän?

213
00:10:38,180 --> 00:10:40,590
En nähnyt tietokonetta
tiede teidän taustalla.

214
00:10:40,590 --> 00:10:42,130
>> -Olemme Saimme vakoojia siellä.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK, Kysytään eri
haastattelu kysymys.

217
00:10:48,444 --> 00:10:49,300
>> [END VIDEOTOISTOSTA]

218
00:10:49,300 --> 00:10:52,290
>> Puhuja: Niin puhuvat
tietty määrä kuitenkin

219
00:10:52,290 --> 00:10:53,890
ei tule olla kaikki hyödyllisiä.

220
00:10:53,890 --> 00:10:56,810
Se ei ole elämän oppitunti että kuplan
lajitella, annetaan miljoonan tulot,

221
00:10:56,810 --> 00:10:58,590
voi kestää jopa 500 miljardia vaiheita.

222
00:10:58,590 --> 00:11:01,120
Ettehän te voi yleistää
liian tehokkaasti, että

223
00:11:01,120 --> 00:11:03,560
ja tehdä hyvää suunnittelua koskeviin päätöksiin
kirjoitettaessa ohjelmia.

224
00:11:03,560 --> 00:11:07,070
Joten keskitytään kuitenkin siihen, miten
voisimme yksinkertaistaa tätä tulosta.

225
00:11:07,070 --> 00:11:11,780
>> Joten olen korostettu keltaisella täällä
tuloksena n ruudutettu jaettuna 2,

226
00:11:11,780 --> 00:11:14,330
joten miljoona potenssiin
jaettuna 2, ja sitten

227
00:11:14,330 --> 00:11:16,710
Olen korostanut, mitä
lopullinen vastaus oli

228
00:11:16,710 --> 00:11:20,180
kun meillä vähennetään pois n jaettuna 2.

229
00:11:20,180 --> 00:11:24,850
Ja väite aion tehdä nyt,
kuka helkutti cares jos vähennetään pois

230
00:11:24,850 --> 00:11:30,060
pieni vanha N yli 2, kun ensimmäinen
osa tätä kaavaa niin paljon isompi?

231
00:11:30,060 --> 00:11:33,910
Se hallitsee muita
Termi, n ruudutettu jaettuna 2

232
00:11:33,910 --> 00:11:37,510
on niin paljon suurempi, selvästi, koska
n saa suuri kuin miljoona,

233
00:11:37,510 --> 00:11:41,450
että on olemassa todella suuri ero on
Päivän päätteeksi välillä 500 miljardia

234
00:11:41,450 --> 00:11:45,730
ja 499999500000?

235
00:11:45,730 --> 00:11:46,349
Ei oikeastaan.

236
00:11:46,349 --> 00:11:48,640
Ja niin mitä aiomme
niin kuin tietotekniikan tutkijoita on

237
00:11:48,640 --> 00:11:53,270
sivuuttaa nämä alemman asteen termit ja
ottaa jotain tällaista ja todella

238
00:11:53,270 --> 00:11:56,050
vain yksinkertaistaa sen
Termi että menee väliä.

239
00:11:56,050 --> 00:12:00,315
Isompi meidän aineistoja saat, isompi
tietokantamme saat, enemmän verkkosivuja

240
00:12:00,315 --> 00:12:02,690
meidän täytyy etsiä, enemmän
ystäviä sinulla Facebookissa.

241
00:12:02,690 --> 00:12:07,340
>> Kuten n suurenee, olemme todella
menossa välitä suurin

242
00:12:07,340 --> 00:12:11,560
aikavälillä tällainen analyysi
algoritmien suorituskykyä.

243
00:12:11,560 --> 00:12:16,230
Ja aion sanoa, tiedätkö mitä,
kupla lajitella on luokkaa iso O,

244
00:12:16,230 --> 00:12:18,060
suuruusluokkaa n potenssiin.

245
00:12:18,060 --> 00:12:20,090
Se ei ole aivan n
potenssiin kuten olemme nähneet,

246
00:12:20,090 --> 00:12:22,060
mutta kuka todella välittää
noista pienempi ehdot,

247
00:12:22,060 --> 00:12:24,390
ja rehellisesti, kuka oikeastaan
kiinnostaa, jos jaamme 2?

248
00:12:24,390 --> 00:12:25,870
Se on vain vakiokertoimella.

249
00:12:25,870 --> 00:12:29,480
Ja on 500 miljardia vs. 250
miljardia todella niin iso juttu?

250
00:12:29,480 --> 00:12:32,190
Voisin vain odottaa vuoden,
anna minun laptop kirjaimellisesti

251
00:12:32,190 --> 00:12:34,810
saat kaksi kertaa nopeammin laitteisto,
ja tuollainen ero

252
00:12:34,810 --> 00:12:36,650
vain menee pois luonnollisesti ajan myötä.

253
00:12:36,650 --> 00:12:39,300
>> Mitä me välitämme on
lauseke, osa

254
00:12:39,300 --> 00:12:42,489
lausekkeen, joka tulee vaihdella
meidän tulo saa isompia ja isompia.

255
00:12:42,489 --> 00:12:45,280
Ja todellakin, todellisessa maailmassa,
niinhän tapahtuu yhä

256
00:12:45,280 --> 00:12:48,330
on tulot ongelmiimme ja
algoritmit ovat yhä suurempia.

257
00:12:48,330 --> 00:12:53,470
Niin iso O tulee olemaan merkintä,
asymptoottinen merkintä, että me vain

258
00:12:53,470 --> 00:12:57,160
käyttää tietotekniikan tutkijoita kuvaamaan
suorituskykyä, tai käyntiaika,

259
00:12:57,160 --> 00:12:58,130
algoritmin.

260
00:12:58,130 --> 00:13:00,800
Jotta voimme vertailla algoritmeja
eri tietokoneissa kirjallisen

261
00:13:00,800 --> 00:13:04,170
eri ihmiset, käyttämällä
Joissakin pohjimmiltaan samanlaisia ​​metrinen

262
00:13:04,170 --> 00:13:07,557
kuten vertailujen lukumäärä olet
tehdä, tai ehkä useita swap

263
00:13:07,557 --> 00:13:08,140
teet.

264
00:13:08,140 --> 00:13:11,910
>> Mitä me aio
määrä on aikaa

265
00:13:11,910 --> 00:13:13,981
joka kulkee kellon
seinälle tyypillisesti.

266
00:13:13,981 --> 00:13:16,230
Mitä emme aio huolehtia
siitä, kuinka paljon muistia

267
00:13:16,230 --> 00:13:17,820
käytät tänään
Ainakin, vaikka se on

268
00:13:17,820 --> 00:13:19,370
toisen resurssin voisimme mitata.

269
00:13:19,370 --> 00:13:23,610
Aiomme yrittää perustaa analyysimme
on vain perustoiminnot, ystävät,

270
00:13:23,610 --> 00:13:25,930
rehellisesti, että voit nähdä visuaalisesti.

271
00:13:25,930 --> 00:13:30,700
Joten jotain iso O n
potenssiin, Väitän, että O n potenssiin

272
00:13:30,700 --> 00:13:35,820
on yläraja on niin kutsuttu
ajoaika kupla lajitella.

273
00:13:35,820 --> 00:13:38,820
Toisin sanoen, jos
halunnut väittää, että on olemassa

274
00:13:38,820 --> 00:13:41,370
tämä yläraja kuinka monta
vaiheet algoritmi voi kestää,

275
00:13:41,370 --> 00:13:46,240
se tulee olemaan iso O n
potenssiin tässä tapauksessa yläraja.

276
00:13:46,240 --> 00:13:49,710
>> Mitä jos sen sijaan muuttaa
Tarina saa olla noin kupla lajitella,

277
00:13:49,710 --> 00:13:50,910
mutta tästä yläraja.

278
00:13:50,910 --> 00:13:54,030
Keksitkö algoritmin
että teimme jo

279
00:13:54,030 --> 00:13:59,530
jonka yläraja, maksimi
mitata aikaa tai toimintaa,

280
00:13:59,530 --> 00:14:04,300
olisi sanoa rajoittamalla
n: llä, lineaarinen funktio,

281
00:14:04,300 --> 00:14:07,260
ei neliöllisesti joka on kaareva?

282
00:14:07,260 --> 00:14:10,780
Mikä algoritmi, joka
aina kestää enempää

283
00:14:10,780 --> 00:14:12,860
kuin esimerkiksi n välein, tai
2n vaiheet, tai 3n vaiheet?

284
00:14:12,860 --> 00:14:13,360
Joo?

285
00:14:13,360 --> 00:14:15,030
>> Yleisö: löytäminen
Suurin numero luettelossa?

286
00:14:15,030 --> 00:14:16,930
>> Puhuja: Perfect löytäminen
suurin numero luettelosta.

287
00:14:16,930 --> 00:14:18,940
Jos olen antanut luettelon
ihmiset esimerkiksi

288
00:14:18,940 --> 00:14:21,440
jokainen, joka on tilalla numero,
mikä on enimmäismäärä

289
00:14:21,440 --> 00:14:23,770
vaiheita se ottaa minua,
kohtuullisen älykäs henkilö,

290
00:14:23,770 --> 00:14:27,530
löytää suurin henkilö kyseisessä luettelossa?

291
00:14:27,530 --> 00:14:28,100
n, eikö?

292
00:14:28,100 --> 00:14:31,320
Koska pahimmassa tapauksessa, jossa
ehkä suurin arvo on?

293
00:14:31,320 --> 00:14:32,700
Aivan, aivan lopussa.

294
00:14:32,700 --> 00:14:34,575
Niin pahimmassa tapauksessa
yläraja, voisin

295
00:14:34,575 --> 00:14:36,450
täytyy mennä aina
tänne ja olla,

296
00:14:36,450 --> 00:14:39,170
Voi, tässä on numero kahdeksan,
tai mitä se arvo on.

297
00:14:39,170 --> 00:14:41,330
Nyt olisi vain tyhmä
jos pidin menossa, eikö?

298
00:14:41,330 --> 00:14:43,840
Etsitkö enemmän ja enemmän elementtejä
jos viimeinen niistä on tuolla?

299
00:14:43,840 --> 00:14:45,340
Niin varmasti, n on yläraja.

300
00:14:45,340 --> 00:14:47,420
Minun ei tarvitse ottaa
enemmän vaiheita kuin.

301
00:14:47,420 --> 00:14:51,580
>> Joten mitä jos sen sijaan ehdotin
olemassa algoritmeja tässä maailmassa

302
00:14:51,580 --> 00:14:57,750
on käynnissä aika, joka on
rajoittamalla iso O log n, log n?

303
00:14:57,750 --> 00:15:00,390
Missä olemme nähneet tämän ennenkin?

304
00:15:00,390 --> 00:15:00,890
Joo?

305
00:15:00,890 --> 00:15:03,309
>> Yleisö: puhelinluettelosta ongelma?

306
00:15:03,309 --> 00:15:04,850
Puhuja: Kuten puhelinluettelo ongelma.

307
00:15:04,850 --> 00:15:07,754
Mikä oli mitata, kuinka
paljon aikaa tai kuinka monta kyyneleet se

308
00:15:07,754 --> 00:15:10,170
vei minut löytää joku
Mike Smith puhelinluettelosta?

309
00:15:10,170 --> 00:15:13,212
Me väittivät olevan log n, ja
vaikka tunne tai se on

310
00:15:13,212 --> 00:15:15,170
hieman utuinen mitä
logaritmi tai eksponentti oli,

311
00:15:15,170 --> 00:15:17,650
vain muistaa, että log n
viittaa yleisesti prosessiin,

312
00:15:17,650 --> 00:15:20,790
Tässä tapauksessa jakamisesta
jotain puoli uudestaan, ja uudestaan,

313
00:15:20,790 --> 00:15:25,790
ja uudestaan, ja uudestaan, niin että se
saa yhä pienempiä kuin sinä, että.

314
00:15:25,790 --> 00:15:28,470
>> Joten päiväkirjaa n viittaa, varma,
puhelinluetteloon esimerkiksi

315
00:15:28,470 --> 00:15:32,662
binary search teoriassa, kun
oli virtuaalinen ovet aluksella,

316
00:15:32,662 --> 00:15:34,370
tai kun Sean oli
etsii jotain.

317
00:15:34,370 --> 00:15:37,374
Jos hän olisi käyttänyt binäärihaku, log n
olisi yläraja sille, kuinka paljon

318
00:15:37,374 --> 00:15:38,040
aika kestää.

319
00:15:38,040 --> 00:15:44,027
Mutta ne algoritmeja, jotka juoksivat
log n oletetaan mitä avain yksityiskohtaisesti?

320
00:15:44,027 --> 00:15:45,360
Että luettelo on lajiteltu, eikö?

321
00:15:45,360 --> 00:15:47,789
Sinun algoritmi on väärä, jos
oma panos ei lajitella,

322
00:15:47,789 --> 00:15:49,830
ja vielä käytät
jotain Binäärihaku

323
00:15:49,830 --> 00:15:51,704
koska saatat hypätä
oikeus yli elementin

324
00:15:51,704 --> 00:15:53,600
tajuamatta sitä on todellakin siellä.

325
00:15:53,600 --> 00:15:55,600
>> Nyt mitä tämä voisi tarkoittaa, iso O yhden?

326
00:15:55,600 --> 00:15:59,117
Tämä ei tarkoita, että algoritmi
otetaan yksi ja vain yksi askel,

327
00:15:59,117 --> 00:16:01,200
se vain tarkoittaa se kestää
jatkuvasti useita vaiheita.

328
00:16:01,200 --> 00:16:04,060
Ehkä se on 1, ehkä se
10, ehkä se on 1000,

329
00:16:04,060 --> 00:16:07,750
mutta se on riippumaton
Ongelman laajuutta.

330
00:16:07,750 --> 00:16:10,850
Ei ole väliä kuinka suuri n on,
jatkuva algoritmi

331
00:16:10,850 --> 00:16:12,747
ottaa aina sama määrä vaiheita.

332
00:16:12,747 --> 00:16:15,080
Joten mikä voisi olla algoritmi
olemme puhuneet tai vain

333
00:16:15,080 --> 00:16:20,418
intuitiivisesti, että tulee teille, että
aina toimii ns vakioaikavälein?

334
00:16:20,418 --> 00:16:20,918
Joo?

335
00:16:20,918 --> 00:16:22,001
>> Yleisö: Lisää kaksi numeroa.

336
00:16:22,001 --> 00:16:25,320
Puhuja: Lisää kaksi numeroa,
2 plus 2 on yhtä kuin 4, tehnyt.

337
00:16:25,320 --> 00:16:27,227
Jotta voisi toimia, mitä muuta?

338
00:16:27,227 --> 00:16:28,560
Entä enemmän todellisessa maailmassa, joo?

339
00:16:28,560 --> 00:16:30,686
>> Yleisö: löytäminen
ensimmäinen asia listalla.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: Finding ensimmäinen
elementti luettelosta varma.

341
00:16:32,810 --> 00:16:34,540
Olemme oikeastaan ​​puhuneet
noin paneelit jo,

342
00:16:34,540 --> 00:16:36,540
miten saat osoitteessa
Ensimmäinen elementti array,

343
00:16:36,540 --> 00:16:40,465
ei väliä kuinka kauan
array on C-koodia?

344
00:16:40,465 --> 00:16:43,090
Käytät vain kuten kiinnike
nolla merkintä, bam, olet siellä.

345
00:16:43,090 --> 00:16:46,120
Ja todellakin paneelit, kuten syrjään,
tukea jotain yleisesti tunnettua

346
00:16:46,120 --> 00:16:49,240
suorasaantiin, random access
muistiin, koska voit kirjaimellisesti

347
00:16:49,240 --> 00:16:50,284
siirtyä mihin tahansa yhteen paikkaan.

348
00:16:50,284 --> 00:16:52,700
Voimme tehdä tämän vielä yksinkertaisemmin
voimme kelata viikko nolla

349
00:16:52,700 --> 00:16:53,900
kun teimme Scratch.

350
00:16:53,900 --> 00:16:59,707
Kuinka kauan se kestää varten
sanoa lohko Scratch toteuttaa?

351
00:16:59,707 --> 00:17:00,790
Vain jatkuva aika, eikö?

352
00:17:00,790 --> 00:17:03,960
Sano jotain, sano
jotain, sillä ei ole väliä

353
00:17:03,960 --> 00:17:07,359
kuinka suuri Naarmut maailma on, se on aina
vie saman verran aikaa

354
00:17:07,359 --> 00:17:08,490
yksinkertaisesti sanoa jotain.

355
00:17:08,490 --> 00:17:11,089
>> Niin, että jatkuva aika,
mutta mitä kääntöpuoli?

356
00:17:11,089 --> 00:17:13,030
Jos se oli ylempi
rajoja, mitä jos me haluamme

357
00:17:13,030 --> 00:17:17,089
kuvaamaan alarajojen
meidän algoritmien ajoaika?

358
00:17:17,089 --> 00:17:19,852
Melkein paras asia
mahdollisesti, jos haluatte,

359
00:17:19,852 --> 00:17:23,060
vaikka näitä termejä voidaan soveltaa parhaiten
tapauksissa, pahimmassa tapauksessa keskimäärin tapausta enemmän

360
00:17:23,060 --> 00:17:26,359
yleisesti, mutta haluan vain keskittyä
on alarajojen yleisemmin.

361
00:17:26,359 --> 00:17:31,920
Mikä algoritmi, joka on
alarajan n vaiheita,

362
00:17:31,920 --> 00:17:33,350
tai 2n vaiheita, tai 3n vaiheet?

363
00:17:33,350 --> 00:17:36,241
Jotkut tekijä n vaiheita,
se on sen alaraja.

364
00:17:36,241 --> 00:17:36,740
Joo?

365
00:17:36,740 --> 00:17:37,910
>> Yleisö: Bubble sort?

366
00:17:37,910 --> 00:17:41,610
>> Puhuja: Bubble sort vie
olet minimaalisesti n vaiheita, miksi?

367
00:17:41,610 --> 00:17:42,279
Miksi näin?

368
00:17:42,279 --> 00:17:45,320
Miksi että alku luoksesi
intuitiivisesti, vaikka se ei ole vain

369
00:17:45,320 --> 00:17:46,530
vielä?

370
00:17:46,530 --> 00:17:47,030
Joo?

371
00:17:47,030 --> 00:17:47,990
>> Yleisö: [kuulumaton].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: Aivan.

374
00:17:52,360 --> 00:17:55,810
Parhaalla mahdollisella skenaario
kupla lajitella ja paljon algoritmeja,

375
00:17:55,810 --> 00:17:58,769
jos annan sinulle kahdeksan ihmistä
jotka ovat jo lajiteltu,

376
00:17:58,769 --> 00:18:00,560
olisi tyhmää
sinulle, algoritmi,

377
00:18:00,560 --> 00:18:02,202
mennä edestakaisin
useammin kuin kerran, eikö?

378
00:18:02,202 --> 00:18:04,285
Koska heti
kävelee listalta, kun,

379
00:18:04,285 --> 00:18:08,090
sinun pitäisi ymmärtää, oh, en tehnyt mitään
swap, tämä luettelo on järjestetty, exit.

380
00:18:08,090 --> 00:18:09,700
Mutta se tulee viemään sinut n toimiin.

381
00:18:09,700 --> 00:18:12,033
>> Ja kääntäen, mitä toinen
tapa ajatella sitä?

382
00:18:12,033 --> 00:18:15,240
Bubble sort on omega,
niin sanotusti n,

383
00:18:15,240 --> 00:18:19,050
koska jos tarkastellaan
Alle n elementtejä, mitä

384
00:18:19,050 --> 00:18:23,009
on perustavanlaatuinen ongelma siellä?

385
00:18:23,009 --> 00:18:24,550
Et tiedä, jos se on järjestetty, oikea.

386
00:18:24,550 --> 00:18:26,800
Me ihmiset mahti vilkaista kahdeksan
ihmisiä ja olla kuin, oh, se lajitellaan,

387
00:18:26,800 --> 00:18:28,430
että ei ottanut minua n toimiin, mutta se teki.

388
00:18:28,430 --> 00:18:30,810
Silmäsi, vaikka laji
ja on suuri näkökenttä,

389
00:18:30,810 --> 00:18:33,184
Oletko katsonut kahdeksan elementtejä,
Oletko katsonut kahdeksan ihmistä,

390
00:18:33,184 --> 00:18:34,610
Se on kahdeksan porrasta tehokkaasti.

391
00:18:34,610 --> 00:18:38,612
Ja vain jos kävelen läpi koko
lista tehdä Ymmärrän kyllä, lajitellaan.

392
00:18:38,612 --> 00:18:41,320
Jos minä puolitiehen ajattelu, kaikki
oikea, se on ihan lajitellaan toistaiseksi,

393
00:18:41,320 --> 00:18:42,520
mitkä ovat kertoimet se ei ole lajiteltu?

394
00:18:42,520 --> 00:18:44,186
Että algoritmit eivät tule olemaan oikea.

395
00:18:44,186 --> 00:18:46,250
Voisi olla nopeampi, mutta väärä.

396
00:18:46,250 --> 00:18:48,500
>> Joten nyt meillä on tapa
kuvaavat alarajoja,

397
00:18:48,500 --> 00:18:49,710
Entä jatkuvasti ajan?

398
00:18:49,710 --> 00:18:54,565
Mikä on algoritmi, joka on pienempi
sitoo sen käyntiaika yksi?

399
00:18:54,565 --> 00:18:58,350
1 askel, 2 askelta, 10 askelta, mutta
vakio, riippumaton n,

400
00:18:58,350 --> 00:18:59,310
koko panos?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Joo, takana.

403
00:19:04,600 --> 00:19:05,309
>> Yleisö: printf?

404
00:19:05,309 --> 00:19:06,183
Puhuja: Mikä tämä on?

405
00:19:06,183 --> 00:19:07,184
Yleisö: printf?

406
00:19:07,184 --> 00:19:07,850
SPEAKER: printf.

407
00:19:07,850 --> 00:19:08,400
OK, varmasti.

408
00:19:08,400 --> 00:19:10,720
Joten se vie kiinteä useita vaiheita.

409
00:19:10,720 --> 00:19:13,170
Ja haluan now-- nyt
puhumme C-koodi

410
00:19:13,170 --> 00:19:16,040
eikä Scratch, jotain
kuten vaikkapa kanssa printf,

411
00:19:16,040 --> 00:19:17,710
meidän pitäisi alkaa saada varovainen.

412
00:19:17,710 --> 00:19:21,090
Koska printf ei ota
tulo, se on merkkijono,

413
00:19:21,090 --> 00:19:23,220
ja jouset eivät teknisesti ole pitkä.

414
00:19:23,220 --> 00:19:25,530
Joten jos haluamme nyt hakemaan
teitä, jos ette pahastu,

415
00:19:25,530 --> 00:19:29,430
Teknisesti voisimme väittää, että printf
ei ota vaihtelevan pituuden tulo,

416
00:19:29,430 --> 00:19:32,270
ja varmasti se voi ottaa enemmän
aika tulostaa merkkijonon tämän pitkän,

417
00:19:32,270 --> 00:19:33,560
kuin tämä pitkä.

418
00:19:33,560 --> 00:19:36,570
>> Joten mitä jos ajatellaan vain
lajittelu ja etsivät esimerkkejä?

419
00:19:36,570 --> 00:19:40,450
Entä Mike Smith puhelimeen
kirja, tai binäärihaku yleisemmin?

420
00:19:40,450 --> 00:19:42,220
Parhaassa tapauksessa, mitä voi tapahtua?

421
00:19:42,220 --> 00:19:45,577
Avaan puhelinluettelosta ja bam,
siellä on Mike Smithin numero.

422
00:19:45,577 --> 00:19:46,660
Voin soittaa hänelle heti.

423
00:19:46,660 --> 00:19:49,390
>> Otti yhden askeleen, ehkä kaksi askelta,
mutta jatkuva useita vaiheita

424
00:19:49,390 --> 00:19:50,230
jos olen onnekas.

425
00:19:50,230 --> 00:19:52,570
Ja suoraan sanottuna, näimme
Maanantai luokkatoverisi

426
00:19:52,570 --> 00:19:54,710
saada varsin onnekas kahdesti peräkkäin.

427
00:19:54,710 --> 00:19:57,050
Ja se oli todellakin jatkuva
aika alarajojen

428
00:19:57,050 --> 00:20:01,280
algoritmin kyseessä löytää
numero 50 jälkeen lopetetuista

429
00:20:01,280 --> 00:20:01,830
ovet.

430
00:20:01,830 --> 00:20:06,400
>> Nyt, kuten syrjään, jos huomaat
että sekä iso O, yläraja,

431
00:20:06,400 --> 00:20:09,310
ja omega, alaraja,
ovat yksi ja sama, että

432
00:20:09,310 --> 00:20:11,830
on sama kaava
suluissa, voit myös

433
00:20:11,830 --> 00:20:15,170
sanoa, vain olla fancy,
että jotain on theta

434
00:20:15,170 --> 00:20:18,270
n: n tai theta jokin muu arvo.

435
00:20:18,270 --> 00:20:20,661
Se tarkoittaa vain sitä, kun iso
O-ja omega ovat samat.

436
00:20:20,661 --> 00:20:21,910
Nyt Entä valinta tavallaan?

437
00:20:21,910 --> 00:20:23,400
Nyt käyttää tätä uutta sanastoa.

438
00:20:23,400 --> 00:20:27,407
Valinnassa lajitella, mitä olimme
tehdä uudelleen ja uudelleen ja uudelleen?

439
00:20:27,407 --> 00:20:29,990
Olin menossa edestakaisin läpi
lista, etsii kenelle?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Pienin luku.

442
00:20:34,730 --> 00:20:37,560
>> Niin kuinka monta askelta, kuinka
monia vertailuja tein

443
00:20:37,560 --> 00:20:43,250
on tehtävä voidakseen selvittää, kuka
pienin elementti listassa oli?

444
00:20:43,250 --> 00:20:44,437
n miinus 1, eikö?

445
00:20:44,437 --> 00:20:47,770
Koska jos vain aloittaa yhden olen
annettu ja aloitan vertaamalla häntä,

446
00:20:47,770 --> 00:20:49,519
Sitten häntä, häntä
tai hänen, häntä, minä

447
00:20:49,519 --> 00:20:52,010
voi parittaa elementtejä
yhdessä n miinus 1 kertaa.

448
00:20:52,010 --> 00:20:55,630
Joten valinta tavallaan samalla otetaan
n miinus 1 vaiheet ensimmäisen kerran.

449
00:20:55,630 --> 00:20:59,540
>> Kuinka monta askelta se vie minut
löytää toiseksi pienin elementti?

450
00:20:59,540 --> 00:21:02,920
n miinus 2, koska olen olla tyhmä
jos pidän katsot samat ihmiset

451
00:21:02,920 --> 00:21:06,280
uudelleen, jos olen jo valinnut hänet
tai hänen ja laita ne paikoilleen.

452
00:21:06,280 --> 00:21:09,270
Ja kolmas vaihe, n
miinus 3, sitten n miinus 4.

453
00:21:09,270 --> 00:21:11,020
Olemme nähneet tämän kuvion
ennen, ja todellakin

454
00:21:11,020 --> 00:21:13,460
valinta tavallaan samalla
on yläraja

455
00:21:13,460 --> 00:21:16,210
n: n potenssiin jos teemme ylös että summattu.

456
00:21:16,210 --> 00:21:19,790
Mikä on sen alaraja, valinta lajitella?

457
00:21:19,790 --> 00:21:25,350
Minimaalisesti, kuinka paljon aikaa must valinta
lajitella ottaa, koska määrittelimme sen maanantaina?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Ehdottaa kahta vaihtoehtoa.

460
00:21:30,490 --> 00:21:32,360
Ehkä se on n, kuten ennen.

461
00:21:32,360 --> 00:21:35,040
Ehkä se on n potenssiin, koska se
on nyt ylärajana.

462
00:21:35,040 --> 00:21:35,874
>> Yleisö: n potenssiin.

463
00:21:35,874 --> 00:21:36,664
Puhuja: n potenssiin.

464
00:21:36,664 --> 00:21:37,368
Miksi?

465
00:21:37,368 --> 00:21:40,060
>> Yleisö: Koska sinulla on
määritellä [kuultavissa].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: Aivan.

467
00:21:41,510 --> 00:21:45,077
Ainakin minä määritellyt valinta tavallaan
se oli aika naiivi, jatkakaa,

468
00:21:45,077 --> 00:21:46,160
löytää pienin elementti.

469
00:21:46,160 --> 00:21:47,770
Mennä uudestaan, löytää pienin elementti.

470
00:21:47,770 --> 00:21:49,490
Mennä uudestaan, löytää pienin elementti.

471
00:21:49,490 --> 00:21:51,700
Ei ole tavallaan
optimointi siellä, että

472
00:21:51,700 --> 00:21:54,350
ehkä haluaisin keskeyttää jälkeen
vain n tai niin vaiheita.

473
00:21:54,350 --> 00:21:57,080
Joten todellakin, valinta
lajitella, omega n potenssiin.

474
00:21:57,080 --> 00:22:00,667
>> Entä lisäyslajittelun, jossa otin
joka minulle annettiin, ja sitten minä plopped häntä

475
00:22:00,667 --> 00:22:01,750
tai hänen oikeassa paikassa?

476
00:22:01,750 --> 00:22:04,958
Sitten aloin toinen henkilö,
plopped hänelle oikea paikka.

477
00:22:04,958 --> 00:22:07,910
Sitten seuraava henkilö, plopped
hänelle oikea paikka.

478
00:22:07,910 --> 00:22:10,537
Huomaa, että tämä on erittäin
lineaarinen, niin sanoakseni.

479
00:22:10,537 --> 00:22:12,620
Olen suora, olen
aio edestakaisin,

480
00:22:12,620 --> 00:22:16,080
En ole koskaan taaksensa todella, mutta
mitä tapahtuu, kun asetan hänet

481
00:22:16,080 --> 00:22:20,302
tai hänet alkuun
lista kuten teimme maanantaina?

482
00:22:20,302 --> 00:22:21,010
Mitä tapahtuu?

483
00:22:21,010 --> 00:22:21,510
Joo?

484
00:22:21,510 --> 00:22:23,122
Yleisö: [kuulumaton].

485
00:22:23,122 --> 00:22:24,830
Puhuja: Joo, että
oli saalis, eikö?

486
00:22:24,830 --> 00:22:26,746
Saatat muistamme
luokkatoverit, jos ne

487
00:22:26,746 --> 00:22:29,670
tekivät mitään liikettä
niiden jalat, jotka oli toiminnassa.

488
00:22:29,670 --> 00:22:33,610
Joten jos siellä oli kolme ihmistä täällä ja
uusi henkilö kuului tuonne,

489
00:22:33,610 --> 00:22:37,360
pitkällä vaiheessa näin, varma, hän
tai hän voi vain mennä loppuun asti.

490
00:22:37,360 --> 00:22:40,074
Mutta jos ajattelemme
tietokone ja erilaisia ​​muistia,

491
00:22:40,074 --> 00:22:41,990
nämä ihmiset ovat menossa
joutua sekoittamaan yli

492
00:22:41,990 --> 00:22:43,260
tehdä tilaa, että henkilö.

493
00:22:43,260 --> 00:22:46,930
Ja niin, että n miinus 1 shufflings,
n miinus 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
miinus 3 shufflings on vain eräänlainen
tapahtuu takanani, ei edessäni

495
00:22:50,660 --> 00:22:52,710
kuten ennen, jossain mielessä.

499
00:22:52,557 --> 00:22:54,640
Nyt syrjään, ja kuten
Olet ehkä nähnyt netissä

500
00:22:54,640 --> 00:22:57,699
jos alkaa tönäisi ympäri noin
lajittelee, siellä on niin paljon erilaisia ​​itse

501
00:22:57,699 --> 00:22:59,490
siellä, jotkut heistä
paremmin kuin toiset.

502
00:22:59,490 --> 00:23:02,200
Todellakin, bogosort on yksi
että on aika hauskaa etsiä.

503
00:23:02,200 --> 00:23:06,650
Bogosort vie joukon
numeroita tai sanoa korttipakan,

504
00:23:06,650 --> 00:23:09,870
satunnaisesti sekoittaa niitä, ja
tarkastukset jos he lajiteltu.

505
00:23:09,870 --> 00:23:12,130
Ja jos ei, tekee sen jälleen.

506
00:23:12,130 --> 00:23:14,140
Ja jos ei, tekee sen jälleen.

507
00:23:14,140 --> 00:23:15,440
Jos ei, ei sitä uudelleen.

508
00:23:15,440 --> 00:23:17,060
Uskomattoman typerä.

509
00:23:17,060 --> 00:23:19,520
>> Ja todellakin, jos luette
kuten Wikipedia,

510
00:23:19,520 --> 00:23:21,200
sen lempinimi on tyhmä tavallaan.

511
00:23:21,200 --> 00:23:25,180
Se lopulta toimii,
toivottavasti, annetaan riittävästi aikaa,

512
00:23:25,180 --> 00:23:28,240
mutta että aikaa
voi kestää jonkin aikaa.

513
00:23:28,240 --> 00:23:31,650
Joten jos voisin, nyt nopeus asioita
ylös Mary Beth esimerkiksi aikaisemmin,

514
00:23:31,650 --> 00:23:35,150
saamalla muutamia elementtejä,
mutta kaksi prosessoria.

515
00:23:35,150 --> 00:23:37,100
Kaksi ihmistä, jos
panisi pahakseni liittyä minua.

516
00:23:37,100 --> 00:23:40,972
Entä 1 tänne, ja
Katsotaanpa go-- kukaan tuolla?

517
00:23:40,972 --> 00:23:41,722
Kukaan tuolla?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Sinulle musta
paita, kyllä, tule alas.

520
00:23:44,190 --> 00:23:45,000
Okei, mikä on nimesi?

521
00:23:45,000 --> 00:23:45,720
>> Yleisö: Peter.

522
00:23:45,720 --> 00:23:46,100
>> Puhuja: Mikä tämä on?

523
00:23:46,100 --> 00:23:46,766
>> Yleisö: Peter.

524
00:23:46,766 --> 00:23:49,450
Puhuja: Peter, David, hauska tavata.

525
00:23:49,450 --> 00:23:53,670
Okei, meillä on Peter täällä, jos
haluavat tulla pöydälle tänne.

526
00:23:53,670 --> 00:23:54,550
Ja mikä on nimesi?

527
00:23:54,550 --> 00:23:55,216
>> Yleisö: Elena.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, kiva tavata.

530
00:23:57,030 --> 00:23:58,060
Elena tavata Peter.

531
00:23:58,060 --> 00:23:59,170
Peter, Elena.

532
00:23:59,170 --> 00:24:02,290
Ja me tarvitsemme Andrew
täällä myös, kiitos.

533
00:24:02,290 --> 00:24:06,107
Ja haaste on menossa
olla lajitella korttipakan.

534
00:24:06,107 --> 00:24:08,190
Ja jos tunne, kannella
korttien pitäisi lopulta

535
00:24:08,190 --> 00:24:11,064
järjestellä vähän jotain
Tässä missä me teemme seurat, sitten

536
00:24:11,064 --> 00:24:13,660
pataa, niin sydämet ja
timantteja, ässästä kuin yksi,

537
00:24:13,660 --> 00:24:15,570
kaikki tavalla jopa kuningas.

538
00:24:15,570 --> 00:24:20,890
>> Kortteja aion antaa teille
tulevat olemaan 52 määrä.

539
00:24:20,890 --> 00:24:23,160
Aiomme samalla
kerran, vain hetken.

540
00:24:23,160 --> 00:24:26,410
Aiomme heittää Andrew
ruudulle täällä,

541
00:24:26,410 --> 00:24:28,170
niin katsella kuin teet tämän.

542
00:24:28,170 --> 00:24:31,070
Ja niin, että kaikki tämän
on vielä näkyvämpää,

543
00:24:31,070 --> 00:24:33,490
nämä ovat kortteja sain Amazon.

544
00:24:33,490 --> 00:24:42,861
Joten ne ovat jo satunnaisesti
lajitellaan, ja aiomme ajoittaa sinua.

545
00:24:42,861 --> 00:24:44,610
Ja me aiomme
pitää se todellinen tällä kertaa,

546
00:24:44,610 --> 00:24:47,820
joten aiomme yrittää painostaa sinua
koska muuten tämä saa ikävä

547
00:24:47,820 --> 00:24:48,460
nopeasti.

548
00:24:48,460 --> 00:24:53,860
Jos voisit edetä lajitella 52
tekijät yhdessä kautta joitakin keinoja, nyt.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Ja taas, kun katselemme näitä
teette mitä, lopulta

551
00:25:07,180 --> 00:25:10,200
aikoo tuottaa ilmeistä
tulos, mieti todella

552
00:25:10,200 --> 00:25:12,962
miten he kukin tekevät sitä,
miten voit kuvailla sitä.

553
00:25:12,962 --> 00:25:15,045
Koska jälleen, nämä ovat
kaikki prosessit, algoritmit

554
00:25:15,045 --> 00:25:17,090
että otamme itsestäänselvyytenä kuin ihmisen.

555
00:25:17,090 --> 00:25:22,349
Mutta olet todennäköisesti jo pitkään ollut
intuitio, kauan ennen kuin edes

556
00:25:22,349 --> 00:25:24,390
ajatellut ottaa
tietojenkäsittelytiede luokka sinua

557
00:25:24,390 --> 00:25:27,223
ehkä ollut intuitio kanssa
joka ratkaista tämänkaltaisia ​​ongelmia.

558
00:25:27,223 --> 00:25:29,560
Mutta kun tunnistat
kuvioita ja alkaa

559
00:25:29,560 --> 00:25:32,407
virallistaa vaiheet, joita
olet ratkaisemaan näitä ongelmia,

560
00:25:32,407 --> 00:25:35,490
huomaat, että voit ratkaista paljon
mielenkiintoinen ja paljon monimutkaisempi

561
00:25:35,490 --> 00:25:39,190
ongelmat nopeasti.

562
00:25:39,190 --> 00:25:42,351
Niin joku yleisöstä, mikä on
ainakin yhden elementin algoritmin

563
00:25:42,351 --> 00:25:43,350
että he käyttävät täällä?

564
00:25:43,350 --> 00:25:44,275
>> Yleisö: [kuulumaton]

565
00:25:44,275 --> 00:25:45,150
Puhuja: Mikä tämä on?

566
00:25:45,150 --> 00:25:47,062
Yleisö: By puku.

567
00:25:47,062 --> 00:25:47,770
Puhuja: By puku.

568
00:25:47,770 --> 00:25:50,630
Joten ensin ne clustering
kaikki timantit yhdessä

569
00:25:50,630 --> 00:25:52,560
se näyttää, kaikki
sydämet yhdessä näyttää siltä,

570
00:25:52,560 --> 00:25:56,520
ja niin edelleen, ilman kunnioitusta
varten numerot kortteja.

571
00:25:56,520 --> 00:26:00,900
Ja nyt ne näkyvät esimerkiksi
voidaan lajittelu lukumäärästä.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Erittäin hyvä.

574
00:26:08,910 --> 00:26:12,370
>> Okei, joten mitä tulee
on viimeinen askel sitten täällä?

575
00:26:12,370 --> 00:26:16,950
Kun meillä on neljä lajiteltua puvut, mitä
meidän täytyy tehdä neljä paalut

576
00:26:16,950 --> 00:26:20,059
jotta saavutetaan yksi
lajiteltu kannella, yksinkertaisesti?

577
00:26:20,059 --> 00:26:21,350
Joten meidän täytyy yhdistää ne uudelleen.

578
00:26:21,350 --> 00:26:25,160
>> Joten on mielenkiintoinen ajatus, että
uudelleen, daresay, on erittäin intuitiivinen jopa

579
00:26:25,160 --> 00:26:28,140
jos et ehkä koskaan löi
tuollainen etiketin.

580
00:26:28,140 --> 00:26:31,900
Tämä perustavanlaatuinen käsite jakamalla
ongelmaa ei puolet tästä ajasta,

581
00:26:31,900 --> 00:26:33,410
mutta vähintään neljään osaan.

582
00:26:33,410 --> 00:26:36,810
Ongelmien melko paljon
pohjimmiltaan samanlaisia ​​ongelmia

583
00:26:36,810 --> 00:26:40,480
erillään toisistaan,
ja sitten yhdistämällä tuloksia.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Ja erinomainen, tehty.

586
00:26:50,140 --> 00:26:52,140
Okei, iso pyöreä
suosionosoitukset, jos voisimme.

587
00:26:52,140 --> 00:26:56,480
>> [APPLAUSE]

588
00:26:56,480 --> 00:26:59,740
>> Puhuja: Minulla ei ole aavistustakaan, mitä sinun
tehdä näillä, mutta tässä mennään.

589
00:26:59,740 --> 00:27:01,690
Kiitos paljon.

590
00:27:01,690 --> 00:27:04,660
Katsotaanpa, kaksi minuuttia
ja kahdeksan sekuntia,

591
00:27:04,660 --> 00:27:07,490
Jos haluat haastaa ystäväsi.

592
00:27:07,490 --> 00:27:12,160
Mitä sitten tulee
olla ottaa pois tästä

593
00:27:12,160 --> 00:27:13,830
että voimme hyödyntää yleisemmin?

594
00:27:13,830 --> 00:27:16,080
No, muistelen
tämä joukko numeroita,

595
00:27:16,080 --> 00:27:19,060
ja muistelen nyt joihinkin
pseudokoodilla olemme kirjoitettu aikaisemmin,

596
00:27:19,060 --> 00:27:22,080
ja tämä oli pseudokoodihajota
ratkaiseminen puhelinluettelo ongelma.

597
00:27:22,080 --> 00:27:25,150
Jolloin pseudokoodilla I
lueteltu systemaattisemmin tavalla

598
00:27:25,150 --> 00:27:28,400
kuvata miten tein erittäin intuitiivinen
ihmisen algoritmi jakamalla puhelimen

599
00:27:28,400 --> 00:27:31,650
kirja puoli, toista, toista, toista,
kunnes löydän jonkun kuten Mike Smith,

600
00:27:31,650 --> 00:27:33,790
jos hän on todellakin puhelinluettelosta.

601
00:27:33,790 --> 00:27:37,610
>> Mutta olen sellainen käyttää mitä soitan
erittäin iteratiivinen lähestymistapa täällä,

602
00:27:37,610 --> 00:27:42,160
erityisesti ilmoituksen rivi 8 ja linja 11.

603
00:27:42,160 --> 00:27:46,750
Nämä ovat todisteita iteratiivinen
lähestymistapa, kiehkura lähestymistapa,

604
00:27:46,750 --> 00:27:49,040
koska se on juuri
käyttäydyttävä aiheuttaa.

605
00:27:49,040 --> 00:27:52,910
Näiden johtojen molemmat sanovat mennä
rivi kolme, ja voit eräänlainen

606
00:27:52,910 --> 00:27:55,140
ajatella, että teidän
sieluni silmin olevan silmukan.

607
00:27:55,140 --> 00:27:59,080
Se kertoo sinua menemään takaisin ylös vaiheeseen
kolme ja toista, uudestaan ​​ja uudestaan,

608
00:27:59,080 --> 00:28:00,010
ja uudelleen.

609
00:28:00,010 --> 00:28:04,410
>> Mutta entä jos me hyödyntää keskeinen ajatus
täällä, että emme viime kerralla,

610
00:28:04,410 --> 00:28:10,280
ja yksinkertaistaa linja 8 ja
linja 11 ja niiden naapureiden

611
00:28:10,280 --> 00:28:12,840
koska juuri tämä, keltainen.

612
00:28:12,840 --> 00:28:16,480
Se ei ole olennaisesti lyhentää
pseudokoodissa erittäin paljon,

613
00:28:16,480 --> 00:28:20,530
mutta se muuttaa olennaisesti
luonne minun algoritmi.

614
00:28:20,530 --> 00:28:24,220
Mitä minä nyt sano
vaiheessa 7, vaiheessa 10,

615
00:28:24,220 --> 00:28:29,140
on etsiä Mike
täsmälleen samalla tavalla,

616
00:28:29,140 --> 00:28:31,580
mutta vain vasemman
puoli tai oikea puoli.

617
00:28:31,580 --> 00:28:33,420
>> Eli toisin sanoen, jos
En aloita vaiheesta yksi,

618
00:28:33,420 --> 00:28:36,150
poimia puhelinluettelosta, avoimia keskellä
ja puhelinluettelosta, katso nimet,

619
00:28:36,150 --> 00:28:39,010
jos Smith on yksi
nimeni, soita Mike, muuta

620
00:28:39,010 --> 00:28:44,340
jos Smith on aiemmin kirja, astu seitsemän
etsi Mike vasemmalla puolella kirja.

621
00:28:44,340 --> 00:28:47,130
Mutta sellainen tuntuu
se jätti minut roikkuu, eikö?

622
00:28:47,130 --> 00:28:49,240
Keltainen, on
opetusta, mutta miten voin

623
00:28:49,240 --> 00:28:51,870
etsi Mike vasemmassa
puolet puhelinluettelosta?

624
00:28:51,870 --> 00:28:54,210
Jossa minulla on
algoritmi, jonka kanssa olen

625
00:28:54,210 --> 00:28:57,100
etsiä joku Mike Smith?

626
00:28:57,100 --> 00:28:58,980
No, se tuijottaa meitä kasvoihin.

627
00:28:58,980 --> 00:29:03,090
Voin kirjaimellisesti käyttää täsmälleen samaa
Ohjelman vaikuttavuus menossa ylös

628
00:29:03,090 --> 00:29:06,490
uudelleen ja uudelleen käynnissä
samaa riviä koodia.

629
00:29:06,490 --> 00:29:10,610
>> Joten vaikka tämä pitäisi tuntea
kuin hieman suhdanteiden määritelmä

630
00:29:10,610 --> 00:29:13,480
jos olet vastaamalla jonkun
kysymys vain eräänlainen kysyä

631
00:29:13,480 --> 00:29:15,990
sama kysymys uudelleen,
kuten miksi, miksi, miksi?

632
00:29:15,990 --> 00:29:21,580
Todellisuus on, koska olemme koodattu
pari erityisen linjat, vaihe 4,

633
00:29:21,580 --> 00:29:25,320
joka on siinä ja vaihe 12, joka
on käytännössä toinen haara,

634
00:29:25,320 --> 00:29:30,120
koska meillä on nämä hätävara toimenpiteitä,
tämä algoritmi päättyy, jos

635
00:29:30,120 --> 00:29:32,050
löytää Mike, tai jos emme.

636
00:29:32,050 --> 00:29:36,810
Mutta vaiheessa 7 ja 10 nyt, meillä on
mitä me kutsumme rekursiivinen algoritmi.

637
00:29:36,810 --> 00:29:40,420
Ja rekursio on todella voimakas ajatus
Se on hiukan mielen taivutus aluksi,

638
00:29:40,420 --> 00:29:42,500
että voimme nyt hakea seuraavasti.

639
00:29:42,500 --> 00:29:46,600
>> Merge sort on viimeinen sort että
katsomme, ainakin luokassa virallisesti.

640
00:29:46,600 --> 00:29:50,040
Ja se on täysin erilainen
Näistä kolme viimeistä, ja varmasti

641
00:29:50,040 --> 00:29:52,140
Viimeisten neljän jos mukaan bogosort.

642
00:29:52,140 --> 00:29:54,810
Tässä pseudokoodihajota yhdistämisen tavallaan.

643
00:29:54,810 --> 00:30:00,170
Kun tulossa n alkion, niin annetaan
taulukon koko n, jos n on pienempi kuin 2,

644
00:30:00,170 --> 00:30:01,040
palata.

645
00:30:01,040 --> 00:30:03,610
Miksi minulla on, että
järki tarkistaa ensin?

646
00:30:03,610 --> 00:30:09,477
Mikä on seuraus, jos annan sinulle
taulukon, jonka pituus on n, on vähemmän kuin 2?

647
00:30:09,477 --> 00:30:11,060
Se on jo lajiteltu, ilmeisesti, eikö?

648
00:30:11,060 --> 00:30:13,640
Koska luettelo on joko
yksi tekijä, joka on trivially

649
00:30:13,640 --> 00:30:15,180
lajiteltu koska se on
Ainoa asia siellä.

650
00:30:15,180 --> 00:30:18,138
Tai, se on kooltaan nolla, mikä tarkoittaa
mikään ei lajitella, joten luonteeltaan

651
00:30:18,138 --> 00:30:18,720
se lajitellaan.

652
00:30:18,720 --> 00:30:20,410
On vain mitään vikaa siellä.

653
00:30:20,410 --> 00:30:22,310
Niin, että meidän ns pohja tapaus.

654
00:30:22,310 --> 00:30:24,440
>> Se on samanlainen henki
mitä teimme Mike.

655
00:30:24,440 --> 00:30:26,023
Jos Mike puhelinluettelosta, soita hänelle.

656
00:30:26,023 --> 00:30:27,740
Jos hän ei ole siellä, anna periksi.

657
00:30:27,740 --> 00:30:31,240
Se on niin sanottu emäs tapauksessa varmistaa,
Tämän algoritmin lopussa päivän

658
00:30:31,240 --> 00:30:33,540
pysähtyy tietyissä olosuhteissa.

659
00:30:33,540 --> 00:30:37,890
>> Mutta tässä uskonvaraisesti nyt muuta,
lajitella vasemmalla puolella elementtejä,

660
00:30:37,890 --> 00:30:39,740
sitten lajitella oikea
puolet elementtejä,

661
00:30:39,740 --> 00:30:41,189
ja sitten yhdistää lajiteltu puolikkaat.

662
00:30:41,189 --> 00:30:43,230
Ja täällä on, jos se tuntuu
kuten olemme copping ulos.

663
00:30:43,230 --> 00:30:46,900
Olen pyytänyt sinua lajitella
n alkiota, ja olen

664
00:30:46,900 --> 00:30:50,712
sanoi OK, tee se lajittelemalla
vasemmalle ja lajittelun oikeassa.

665
00:30:50,712 --> 00:30:52,420
Mutta sanon yhden
Toinen asia, ja tämä

666
00:30:52,420 --> 00:30:55,530
on keskeinen teema näyttää
vuonna intuitio toistaiseksi,

667
00:30:55,530 --> 00:30:57,380
on tämä kolmas vaihe sulauttaa.

668
00:30:57,380 --> 00:31:00,430
Joka vaikka se
tuntuu niin tyhmä hengessä,

669
00:31:00,430 --> 00:31:02,320
kuin vain yhdistää asiat
yhdessä, se näyttää

670
00:31:02,320 --> 00:31:05,380
olla tärkeä askel kohti
Kokoa kaksi ongelmaa

671
00:31:05,380 --> 00:31:07,330
jaettiin lopulta kahtia.

672
00:31:07,330 --> 00:31:12,090
>> Joten yhdistää lajitella, tehdään tämä, jos sinulla
huumori minulle, yksi enemmän esittelyä,

673
00:31:12,090 --> 00:31:14,730
juuri niin, että meillä on joitakin
numerot työskennellä.

674
00:31:14,730 --> 00:31:19,470
Voinko vaihtaa kahdeksan stressiä
pallot kahdeksan ihmistä?

675
00:31:19,470 --> 00:31:29,320
Okei, entä te kolme, neljä erilaista
Tässä jaksossa, viisi, kuusi, ja lähdetään

676
00:31:29,320 --> 00:31:30,720
älä 7, 8, tule ylös.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, joo OK.

679
00:31:36,520 --> 00:31:38,640
+8, Siellä mennään, plus 1.

680
00:31:38,640 --> 00:31:39,150
Erinomainen.

681
00:31:39,150 --> 00:31:42,000
Okei Tule ylös, katsotaanpa
nopeasti saat numeroita.

682
00:31:42,000 --> 00:31:50,800
Numero kaksi, numero kolme, numero neljä,
numero viisi, kuusi, seitsemän ja kahdeksan.

683
00:31:50,800 --> 00:31:52,140
Tein kahdeksan oikein tällä kertaa.

684
00:31:52,140 --> 00:31:56,390
>> OK, niin mene eteenpäin jos voisit, ja
Katsotaanpa lajitella alkuperäisessä järjestyksessä

685
00:31:56,390 --> 00:31:59,810
että meillä oli eilen jossa tarkasteltiin
näin, jos et mielessä.

686
00:31:59,810 --> 00:32:03,620
Ja tehdään se edessä pöytä.

687
00:32:03,620 --> 00:32:06,510
Okei, joten yhdistää tavallaan.

688
00:32:06,510 --> 00:32:08,820
Tämä on, jos se menee
saada sellainen mielenkiintoinen,

689
00:32:08,820 --> 00:32:12,800
koska en näy antavan itselleni
niin paljon vähemmän tietoa tänään.

690
00:32:12,800 --> 00:32:15,149
>> Joten yhdistää eräänlainen ensinnäkin
Tulon n alkion,

691
00:32:15,149 --> 00:32:18,440
ja ei tietenkään ole vähemmän kuin kaksi, se on
kahdeksan, joten minulla on jonkin verran enemmän työtä.

692
00:32:18,440 --> 00:32:21,140
Joten nyt henkisesti me luokkana
ovat nyt muuten haara,

693
00:32:21,140 --> 00:32:22,540
mikä tarkoittaa sitä, kolme vaihetta.

694
00:32:22,540 --> 00:32:25,017
Ensinnäkin minun täytyy lajitella
vasen puoli elementtejä.

695
00:32:25,017 --> 00:32:26,350
Joten miten edetä tässä?

696
00:32:26,350 --> 00:32:28,950
No, aion sellaista
henkisesti jakaa listan täällä,

697
00:32:28,950 --> 00:32:30,700
sinun ei tarvitse
fyysisesti liikkua, ja olen

698
00:32:30,700 --> 00:32:33,180
aio keskittyä vain
vasen puoli elementteinä tässä.

699
00:32:33,180 --> 00:32:36,770
Joten miten pääsen lajittelu
lista nyt koosta neljä?

700
00:32:36,770 --> 00:32:38,730
Mikä on minun algoritmi?

701
00:32:38,730 --> 00:32:42,580
Ensin tarkistettava n alle kaksi, no,
joten en jatka muuta lohkon uudelleen.

702
00:32:42,580 --> 00:32:43,900
Järjestä vasen puoli elementtejä.

703
00:32:43,900 --> 00:32:45,608
>> Joten nyt taas, henkisesti,
ja tässä

704
00:32:45,608 --> 00:32:49,550
joudut kertyy paljon
henkistä historiaa, jos haluatte.

705
00:32:49,550 --> 00:32:51,940
Nyt olen lajittelu vasen
puolet vasen puoli.

706
00:32:51,940 --> 00:32:57,000
Okei, joten nyt soitan saman yhdistämisen
Lajittelualgoritmi, on N alle kaksi?

707
00:32:57,000 --> 00:33:00,590
Ei, se on kaksi, joten minun täytyy lajitella
vasen puoli ja oikea puoli.

708
00:33:00,590 --> 00:33:02,042
Joten tässä sitä mennään, lajitella vasen puoli.

709
00:33:02,042 --> 00:33:03,750
Miksi et vain
ottaa yksi askel eteenpäin.

710
00:33:03,750 --> 00:33:04,415
Mikä sinun nimesi on?

711
00:33:04,415 --> 00:33:04,860
>> Yleisö: Darren.

712
00:33:04,860 --> 00:33:05,260
>> SPEAKER: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan on astunut eteenpäin.

714
00:33:06,040 --> 00:33:06,748
>> Yleisö: Darren.

715
00:33:06,748 --> 00:33:09,000
Puhuja: Darren, tehty.

716
00:33:09,000 --> 00:33:10,090
Sanoit Darren tai Dan?

717
00:33:10,090 --> 00:33:10,550
>> Yleisö: Darren.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren on lisännyt
eteenpäin ja hän on nyt järjestetty.

720
00:33:14,422 --> 00:33:16,130
Ja tämä on melkein
typerä väite, eikö?

721
00:33:16,130 --> 00:33:18,862
En todellakaan tunnu saavuttamaan
mitään, mutta katsotaan eteenpäin.

722
00:33:18,862 --> 00:33:20,820
Nyt haluaisin lajitella oikea
puolet elementtejä.

723
00:33:20,820 --> 00:33:21,200
Mikä sinun nimesi on?

724
00:33:21,200 --> 00:33:21,690
>> Yleisö: Luke.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: Luke.

726
00:33:22,273 --> 00:33:23,400
Tule, astu eteenpäin.

727
00:33:23,400 --> 00:33:25,640
Tehty olen lajiteltu Luke.

728
00:33:25,640 --> 00:33:28,570
Vasen puoli on nyt lajitellaan ja
oikea puoli on nyt järjestetty,

729
00:33:28,570 --> 00:33:30,770
mutta jälleen kerran, siellä on tärkeä askel tässä.

730
00:33:30,770 --> 00:33:32,940
Mitä minun seuraavaksi pitää tehdä?

731
00:33:32,940 --> 00:33:33,941
Yhdistä lajiteltu puolikkaat.

732
00:33:33,941 --> 00:33:36,648
Nyt aiomme vain
jokainen edestakaisin tällä tavalla,

733
00:33:36,648 --> 00:33:38,620
koska olen sellainen tarvitaan
Joissakin työtilaa.

734
00:33:38,620 --> 00:33:40,411
Se on melkein kuin nämä
kaverit ovat pöydällä,

735
00:33:40,411 --> 00:33:42,460
ja minä tarvitsen tilaa
siirtää niitä ympäriinsä.

736
00:33:42,460 --> 00:33:44,170
Joten aion yhdistää
te tarkastelemalla

737
00:33:44,170 --> 00:33:45,960
klo vasen puoli ja oikea puoli.

738
00:33:45,960 --> 00:33:48,740
Ja joka ilmeisesti tulee ensin,
vasen puoli tai oikea puoli?

739
00:33:48,740 --> 00:33:52,710
Joten oikea puoli, joten lähdetään Luke yli
tästä Darren alkuperäiseen asentoon.

740
00:33:52,710 --> 00:33:57,640
Ja nyt yhdistämään vasen puoli on,
Darren tulee liikkua tuolla.

741
00:33:57,640 --> 00:33:59,750
>> Joten tuntuu melkein
kupla lajitella vaikutus,

742
00:33:59,750 --> 00:34:02,482
mutta perustavanlaatuinen algoritmi,
hyvin erilaisia ​​tällä kertaa.

743
00:34:02,482 --> 00:34:04,815
Mutta nyt on, jos asiat saavat
vähän ärsyttävää, koska olet

744
00:34:04,815 --> 00:34:06,810
täytyy kelata henkisesti
Mistä lähden pois.

745
00:34:06,810 --> 00:34:09,893
Olen juuri yhdistänyt lajitellut puoliskot,
mikä tarkoittaa Olen jos minun algoritmi?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Minun täytyy lajitella oikea puoli, oikea?

748
00:34:13,770 --> 00:34:15,910
>> Jos kelaat, kirjaimellisesti
videon, voit

749
00:34:15,910 --> 00:34:18,339
nähdä, että saimme tähän
pisteen Luke ja Darren

750
00:34:18,339 --> 00:34:21,370
lajittelemalla vasemman
puolet vasen puoli.

751
00:34:21,370 --> 00:34:23,430
Sitten yhdistimme ne
lajitellut puoliskot, joka

752
00:34:23,430 --> 00:34:27,941
tarkoittaa seuraava askel on eräänlainen
oikea puoli vasen puoli.

753
00:34:27,941 --> 00:34:29,649
Okei, joten katsotaanpa
tehdä tämän nopeammin.

754
00:34:29,649 --> 00:34:33,282
Okei, kuusi, aion vaatia
olet nyt selvittäneet, tule esiin.

755
00:34:33,282 --> 00:34:33,990
Mikä sinun nimesi on?

756
00:34:33,990 --> 00:34:34,589
>> Yleisö: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano on nyt järjestetty.

759
00:34:36,010 --> 00:34:36,450
Ja mikä on nimesi?

760
00:34:36,450 --> 00:34:37,080
>> Yleisö: Alex.

761
00:34:37,080 --> 00:34:38,379
>> Puhuja: Alex on nyt järjestetty.

762
00:34:38,379 --> 00:34:40,750
Vasen puoli, oikea puoli,
mikä on viimeinen vaihe?

763
00:34:40,750 --> 00:34:41,250
Yhdistä.

764
00:34:41,250 --> 00:34:44,310
Melko triviaali, joten olen
menossa yhdistää kuudessa,

765
00:34:44,310 --> 00:34:46,930
ottaa askel taaksepäin,
kahdeksan, ottaa askel taaksepäin.

766
00:34:46,930 --> 00:34:49,530
Ja nyt huomaa tämä on
hyödyllinen takeaway, mitä

767
00:34:49,530 --> 00:34:53,930
on nyt totta noin vasen puoli
lista, riippumatta siitä, miten aloitimme?

768
00:34:53,930 --> 00:34:55,090
Se lajitellaan.

769
00:34:55,090 --> 00:34:57,750
>> Nyt se ei ole lajiteltu
suuri järjestelmässä asioita,

770
00:34:57,750 --> 00:35:00,250
mutta se on järjestetty itsenäisesti
ja toinen puoli.

771
00:35:00,250 --> 00:35:04,100
Mitä nyt askel Olenko jos pidän
kelauksen miten tarina alkoi?

772
00:35:04,100 --> 00:35:05,680
Nyt minun täytyy lajitella oikea puoli.

773
00:35:05,680 --> 00:35:07,630
Joten nyt olemme paluumatkalla
tarinan alku,

774
00:35:07,630 --> 00:35:08,921
ja tehdään tämä nopeammin.

775
00:35:08,921 --> 00:35:11,320
Joten aion lajitella
oikea puoli koko lista.

776
00:35:11,320 --> 00:35:13,060
Mikä on seuraava askel?

777
00:35:13,060 --> 00:35:15,840
Lajitella vasen puoli oikea puoli.

778
00:35:15,840 --> 00:35:18,715
Lajitella vasen puoli
vasen puoli ja oikea puoli.

779
00:35:18,715 --> 00:35:19,590
Ja mikä on nimesi?

780
00:35:19,590 --> 00:35:20,230
>> Yleisö: Omar.

781
00:35:20,230 --> 00:35:21,970
>> Puhuja: Omar, askel eteenpäin, tehty.

782
00:35:21,970 --> 00:35:22,860
Vasen puoli on lajiteltu.

783
00:35:22,860 --> 00:35:23,330
Ja mikä on nimesi?

784
00:35:23,330 --> 00:35:23,820
>> Yleisö: Chris.

785
00:35:23,820 --> 00:35:25,620
>> Puhuja: Chris, ottaa askel
eteenpäin, olet nyt lajitellaan.

786
00:35:25,620 --> 00:35:27,010
Mikä on tärkeä askel nyt?

787
00:35:27,010 --> 00:35:27,510
Yhdistä.

788
00:35:27,510 --> 00:35:30,509
Niin yksi on menossa yhdistää paikalleen
täällä, jos voisit ottaa askel taaksepäin,

789
00:35:30,509 --> 00:35:32,930
ja kolme on menossa
ottaa askel taaksepäin, yhdistää.

790
00:35:32,930 --> 00:35:38,080
Joten vasen puoli
oikea puoli, on nyt järjestetty.

791
00:35:38,080 --> 00:35:41,747
Suoraan sanottuna tämä algoritmi tuntuu kuin olisimme
tuhlaavat paljon enemmän aikaa kuin ennen,

792
00:35:41,747 --> 00:35:44,830
mutta jos emme tällä reaaliajassa, me
mitä noutoruokapaikkoja olemaan.

793
00:35:44,830 --> 00:35:47,970
Nyt tässä olen, oikea
puolet oikea puoli,

794
00:35:47,970 --> 00:35:50,170
anna minun mennä eteenpäin ja lajitella vasen puoli.

795
00:35:50,170 --> 00:35:51,482
Askel eteenpäin, mikä on nimesi?

796
00:35:51,482 --> 00:35:52,190
Yleisö: Ramsey.

797
00:35:52,190 --> 00:35:53,210
Puhuja: Ramsey on nyt järjestetty.

798
00:35:53,210 --> 00:35:53,570
Mikä sinun nimesi on?

799
00:35:53,570 --> 00:35:54,200
>> Yleisö: Marina.

800
00:35:54,200 --> 00:35:57,033
>> Puhuja: Marina on nyt lajitellaan
hyvin, jos otat yhden askeleen eteenpäin.

801
00:35:57,033 --> 00:36:00,690
Tärkeä askel tässä on nyt yhdistää, olen
menossa nyppiä minun kaksi listaa,

802
00:36:00,690 --> 00:36:01,720
vasemmalle ja oikealle.

803
00:36:01,720 --> 00:36:05,150
Viisi näistä tulee ensin,
ja seitsemän on tulossa seuraavaksi.

804
00:36:05,150 --> 00:36:06,410
Ja vielä, tämä on tarkoituksellista.

805
00:36:06,410 --> 00:36:08,535
Se, että he ottavat
astuu esiin ja takaisin

806
00:36:08,535 --> 00:36:12,997
on tarkoitus edustaa, että emme voi
tehdä tämän algoritmin sijasta yhtä helposti

807
00:36:12,997 --> 00:36:15,830
kuten kupla lajitella, ja valinta lajitella,
ja lisäyslajittelun missä vain

808
00:36:15,830 --> 00:36:16,960
säilytetään vaihtamalla ihmiset.

809
00:36:16,960 --> 00:36:19,940
Olen kirjaimellisesti tarvitse lajitella
tyhjästä paperi, jossa

810
00:36:19,940 --> 00:36:21,827
laittaa nämä ihmiset
Vaikka en yhdistäminen,

811
00:36:21,827 --> 00:36:23,410
ja sitten voin laittaa ne takaisin paikoilleen.

812
00:36:23,410 --> 00:36:27,260
Ja se on avain, koska käytän
uusi resurssi, tila, eikä vain kerran.

813
00:36:27,260 --> 00:36:28,270
>> OK, tämä on hämmästyttävä.

814
00:36:28,270 --> 00:36:32,050
Vasen puoli lajitellaan, oikea puoli on
lajitellut, nyt kun avain sulautuvan askel.

815
00:36:32,050 --> 00:36:33,450
Miten minä sulauttamisesta?

816
00:36:33,450 --> 00:36:35,470
Joten jos voit seurata minun
vasen käsi ja oikea käsi,

817
00:36:35,470 --> 00:36:38,930
Aion tuoda vasempaan käteeni
vasemmalla puolen, minun oikea käteni

818
00:36:38,930 --> 00:36:42,680
oikealla puolen, ja nyt minun täytyy
päättää askel askeleelta kenen yhdistyä.

819
00:36:42,680 --> 00:36:44,650
Joka ilmeisesti tulee ensin?

820
00:36:44,650 --> 00:36:45,150
Numero yksi.

821
00:36:45,150 --> 00:36:47,327
Joten tule tänne,
tässä on meidän muistilehtiö.

822
00:36:47,327 --> 00:36:49,910
Joten nyt ykköseksi, ja huomautus
mitä teen minun oikealle puolelleni,

823
00:36:49,910 --> 00:36:54,152
Aion siirtyä minun oikea käteni yksi
askel yli kohtaan numero kolme,

824
00:36:54,152 --> 00:36:55,860
ja nyt minun täytyy tehdä
saman päätöksen.

825
00:36:55,860 --> 00:36:58,387
Ja seisoa aivan
edessä Luke täällä jos voisit,

826
00:36:58,387 --> 00:36:59,720
koska tämä on meidän muistilehtiö.

827
00:36:59,720 --> 00:37:00,610
Joten kuka tulee seuraavaksi?

828
00:37:00,610 --> 00:37:05,000
Meillä Luukas on numero kaksi
tai Chris numerolla kolme.

829
00:37:05,000 --> 00:37:07,460
Ilmeisesti Luke, numero
kaksi, niin tulet tänne.

830
00:37:07,460 --> 00:37:11,270
>> Mutta minun vasen käsi nyt on menossa
kasvatetaan pisteeseen Darren,

831
00:37:11,270 --> 00:37:15,160
ja tässä on avain ottaa pois
yhdistäminen, aion jatkaa tätä,

832
00:37:15,160 --> 00:37:17,340
tietenkin, jos sellainen
ja noudata logiikkaa.

833
00:37:17,340 --> 00:37:19,670
Mutta käteni ovat koskaan
menossa taaksepäin,

834
00:37:19,670 --> 00:37:23,861
mikä tarkoittaa En vain koskaan siirtymässä
jää minun yhdistäminen prosessi,

835
00:37:23,861 --> 00:37:26,360
ja että tulee olemaan avain
Analyysissä vain hetken.

836
00:37:26,360 --> 00:37:27,859
>> Joten nyt Lopetetaan tämä ylös nopeasti.

837
00:37:27,859 --> 00:37:31,650
Joten kolme tulee seuraavaksi,
sitten neljä tulee seuraavaksi,

838
00:37:31,650 --> 00:37:38,750
ja nyt viisi tulee seuraavaksi, sitten kuusi,
ja seitsemän, ja sitten lopulta kahdeksan.

839
00:37:38,750 --> 00:37:42,960
Tuntuu hitain algoritmi
vielä, mutta ei jos me todella

840
00:37:42,960 --> 00:37:45,510
sen käydä samanlaista
kellon nopeus, niin

841
00:37:45,510 --> 00:37:48,106
puhua, joilla on sama
tikittävä kello kuten ennen.

842
00:37:48,106 --> 00:37:48,605
Miksi?

843
00:37:48,605 --> 00:37:51,100
No, Otetaanpa
katso lopputulos.

844
00:37:51,100 --> 00:37:56,990
>> Mennään takaisin tänne, haluan
vedä ylös esittelyä visuaalisesti

845
00:37:56,990 --> 00:37:59,030
mitä me vain teimme.

846
00:37:59,030 --> 00:38:06,110
Suurentamalla täällä, tässä
sivu täällä, kertoo Firefox

847
00:38:06,110 --> 00:38:08,200
että haluamme jonoon
ylös tähän kohtaan, katsotaanpa

848
00:38:08,200 --> 00:38:11,260
sanoa kupla lajitella, jonka kanssa
olemme nyt hyvin tuttu,

849
00:38:11,260 --> 00:38:14,130
valinta sort, joka on toinen
melko selkeältä yksi,

850
00:38:14,130 --> 00:38:18,250
ja nyt tänään yhdistämisen sort, joka
on meidän loppuhuipennukseen.

851
00:38:18,250 --> 00:38:21,530
Siksi kesti niin paljon kauemmin
täällä ihmisiin ja minua sanallisesti on,

852
00:38:21,530 --> 00:38:23,480
tietenkin, olen selittää jokainen askel.

853
00:38:23,480 --> 00:38:26,920
Mutta jos vain suorittaa tämän, paljon
kuten teimme kupla lajitella ja valinta

854
00:38:26,920 --> 00:38:30,890
lajitella paitsi visuaalisesti, watch
kuinka paljon tehokkaammin

855
00:38:30,890 --> 00:38:33,330
tämä hankittua
jako ja valloittaa

856
00:38:33,330 --> 00:38:39,150
voi, kun sitä käytetään tietojen joukko, joka on
ei edes koko kahdeksan, mutta jopa paljon,

857
00:38:39,150 --> 00:38:39,970
paljon suurempi.

858
00:38:39,970 --> 00:38:44,585
Annan sinulle yhdistää lajitella, rinta
puolelta näitä muita algoritmeja.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Tämä on menossa tuskallista
nopeasti, ja loppu

861
00:38:58,530 --> 00:39:00,890
ei ole erityisen huipussaan,
ne vain päätyvät lajiteltu.

862
00:39:00,890 --> 00:39:05,280
Mutta avain ottaa pois on se, että
Katso kuinka paljon nopeammin yhdistää lajitella

863
00:39:05,280 --> 00:39:08,110
oli, ellet usko, että olen
juuri sellainen pilailin.

864
00:39:08,110 --> 00:39:13,100
Jos teemme tämän viimeisen kerran,
Katsotaanpa lataa tämä, mennään takaisin

865
00:39:13,100 --> 00:39:14,960
ja valitse kupla lajitella,
ja ihan vain huvin vuoksi,

866
00:39:14,960 --> 00:39:17,330
valitkaamme lisäys
lajitella, vain hyvä toimenpide.

867
00:39:17,330 --> 00:39:20,020
Ja tällä kertaa taas, nyt
Valitse Yhdistämisen lajitella ja lähdetään

868
00:39:20,020 --> 00:39:21,595
todella ajaa näitä rinnakkain.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Ja se ei ole, itse asiassa onnenpotku.

871
00:39:26,930 --> 00:39:31,140
Mitä olen noudattanut tätä on olen
jaettu minun panos puoli, jälleen,

872
00:39:31,140 --> 00:39:32,240
ja uudestaan, ja uudestaan.

873
00:39:32,240 --> 00:39:35,590
Ja siellä on vain niin monta kertaa voit
jakaa teidän panos kahtia, vasen

874
00:39:35,590 --> 00:39:36,240
ja oikea.

875
00:39:36,240 --> 00:39:39,425
Mikä kaava, että meillä pitää nähdä
joka kuvaa jako kahtia

876
00:39:39,425 --> 00:39:41,050
uudestaan, ja uudestaan, ja uudestaan, ja uudestaan?

877
00:39:41,050 --> 00:39:41,890
>> Yleisö: log n.

878
00:39:41,890 --> 00:39:42,760
>> Puhuja: log n.

879
00:39:42,760 --> 00:39:46,300
Mutta sitten on yksi toinen tärkeä askel,
tämä algoritmi ei log n vaiheita.

880
00:39:46,300 --> 00:39:48,992
Jos se oli vain log n vaiheita,
meillä olisi sama ongelma

881
00:39:48,992 --> 00:39:51,200
kuin ennen, jossa emme voi olla
että kaikki on järjestetty.

882
00:39:51,200 --> 00:39:54,480
Sinun täytyy vähän katsoa n osia
olla varma n elementit lajitellaan,

883
00:39:54,480 --> 00:39:55,950
muuten se uskonvaraisesti.

884
00:39:55,950 --> 00:39:59,810
>> Joten se on vähän log n vaiheita, mutta
Entä tämä avain yhdistäminen vaihe

885
00:39:59,810 --> 00:40:04,370
jossa olen sulautunut minun vasen puoli ja oikea
puoli ja käveli poikki vaiheessa?

886
00:40:04,370 --> 00:40:06,980
Kuinka monta askelta on, että yhdistää?

887
00:40:06,980 --> 00:40:10,150
Se on n, mutta en vain
yhdistää viimeisen kerran.

888
00:40:10,150 --> 00:40:15,089
Kullekin näistä sisäkkäisiä puheluita, kullakin
Näiden sisäkkäisiä yhdistämisiä, olen edelleen lajitellaan.

889
00:40:15,089 --> 00:40:18,380
Olen yhdistettiin nämä kaksi kaveria, niin nämä kaksi
kaverit, niin nämä kaksi kaveria ja niin edelleen.

890
00:40:18,380 --> 00:40:19,955
>> Joten en sulautuvat uudestaan, ja uudestaan.

891
00:40:19,955 --> 00:40:20,580
Kuinka monta kertaa?

892
00:40:20,580 --> 00:40:23,510
Niin joka kerta olen jakanut
alalta puoli, tein yhdistämisen.

893
00:40:23,510 --> 00:40:25,460
Jakaa listan kahtia, tehdä yhdistämisen.

894
00:40:25,460 --> 00:40:28,570
Joten jos jakamalla luettelo
voidaan tehdä log n kertaa,

895
00:40:28,570 --> 00:40:33,880
ja yhdistäminen lopulta vie n
vaiheet, mikä voisi olla nyt ylemmän

896
00:40:33,880 --> 00:40:37,000
sidottu käynnissä
aika meidän algoritmi?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Ja todellakin, niinhän
olemme saaneet aikaan täällä.

899
00:40:40,560 --> 00:40:44,650
Niin tuntuu että näet visuaalisesti, kun
nämä kolme asiaa kulkevat rinnakkain

900
00:40:44,650 --> 00:40:47,930
on n potenssiin vastaan ​​n
potenssiin vastaan ​​n log n.

901
00:40:47,930 --> 00:40:51,010
Joka pohjimmiltaan näemme,
ei vain tänään, vaan myös tulevaisuudessa,

902
00:40:51,010 --> 00:40:52,760
on paljon, paljon nopeammin.

903
00:40:52,760 --> 00:40:56,010
Aplodit nämä kaverit,
Aion palkita heitä stressiä pallot.

904
00:40:56,010 --> 00:41:00,260
Katsotaanpa lykätä täällä tänään, ja
näemme sinut maanantaina.

905
00:41:00,260 --> 00:41:02,255