1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Viikko 3, jatkuu]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Harvardin yliopisto]

3
00:00:04,110 --> 00:00:07,130
>> [Tämä on CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Selvä. Tervetuloa takaisin. Tämä on CS50 ja tämä on loppuviikosta 3.

5
00:00:11,010 --> 00:00:14,680
>> Joten ne tunne, viime vuonna Harvardin käynnistänyt mitä kutsutaan Innovation Lab,

6
00:00:14,680 --> 00:00:18,530
tai i-lab, joka on ihana rakennuksen koko joen HBS: n kampuksella

7
00:00:18,530 --> 00:00:22,640
joka on avoin opiskelijoiden, GSA opiskelijoita, opiskelijoita eri puolilta kampuksella,

8
00:00:22,640 --> 00:00:27,000
lukien tiedekunnan, ja se on paikka kokoontua työskennellä innovatiivisia asioita,

9
00:00:27,000 --> 00:00:29,180
erityisesti yrittäjyyteen asiat

10
00:00:29,180 --> 00:00:33,410
jos ja 0 tai enemmän ystäviä ajatellut tehdä jotain yrittäjyyteen

11
00:00:33,410 --> 00:00:37,080
joko aikana tässä luokassa, sen jälkeen kun tämän luokan, tai sen jälkeen.

12
00:00:37,080 --> 00:00:41,540
>> Joten yksi niistä asioista, he tekevät yli J aikavälillä on näitä matkoja,

13
00:00:41,540 --> 00:00:44,510
joista yksi on New York, joista yksi on Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Avaruus on hyvin rajallinen, mutta se on mahdollisuus hieroa hartioita MBA

15
00:00:47,530 --> 00:00:52,200
ja jatko-opiskelijoille eri kampuksella ja todella viettää aikaa näillä alueillaan

16
00:00:52,200 --> 00:00:55,500
chattailuun up startups, chattailuun yrittäjien ja vastaavat.

17
00:00:55,500 --> 00:00:57,870
Eli jos kiinnostaa, tutustu tähän URL täällä.

18
00:00:57,870 --> 00:01:01,220
Se on saatavilla myös dioja verkossa.

19
00:01:01,220 --> 00:01:04,610
>> Voisimmeko lieventää House Audio vain vähän?

20
00:01:04,610 --> 00:01:08,640
Jos haluat liittyä meihin lounas perjantaina, 13:15 Fire & Ice, ota suunnata sinne.

21
00:01:08,640 --> 00:01:11,390
Pahoittelut jos lomake on jo täytetty, kun pääset sinne.

22
00:01:11,390 --> 00:01:13,750
Mutta me jatkamme tätä perinnettä eteenpäin.

23
00:01:13,750 --> 00:01:17,350
>> Tänään jatkamme korkeampi keskustelua erilaisista ongelmista, että voimme ratkaista,

24
00:01:17,350 --> 00:01:21,330
keskitytään paljon vähemmän, ainakin tänään on koodi ja paljon ideoita.

25
00:01:21,330 --> 00:01:24,720
Joten muistelen viikolla 0, kun me repäisi puhelinluettelon kahtia,

26
00:01:24,720 --> 00:01:28,260
jonka tavoitteena oli tehdä jotain, tosin hieman dramaattinen

27
00:01:28,260 --> 00:01:32,360
mutta lähettää siihen pisteeseen, että hakua ei tarvitse olla välttämättä,

28
00:01:32,360 --> 00:01:35,100
yhtä selvää ensi silmäyksellä kuin luulisi.

29
00:01:35,100 --> 00:01:40,200
Ja ongelmanratkaisussa yleensäkin eivät välttämättä aina paras -

30
00:01:40,200 --> 00:01:44,130
Ilmeisin ratkaisu ei välttämättä olla paras.

31
00:01:44,130 --> 00:01:47,300
Joten meillä oli tämä puhelinluettelosta ja suoraan sanottuna, me kaikki tässä huoneessa oli vaistot,

32
00:01:47,300 --> 00:01:51,470
todennäköisimmin, alkaa keskellä etsiessään Mike Smith ja siirry sitten vasemmalle tai oikealle

33
00:01:51,470 --> 00:01:54,280
perustua johonkin kirjainmerkki meidän sattui päätyä.

34
00:01:54,280 --> 00:01:57,560
>> Mutta pelkkä ajatus, että me ihmiset olemme itsestään niin kauan

35
00:01:57,560 --> 00:02:00,670
oikeastaan ​​pitäisi alkaa tulemaan eturintamassa mieltäsi

36
00:02:00,670 --> 00:02:03,900
koska sillä ongelmia saada paljon monimutkaisempi kuin puhelinluettelo,

37
00:02:03,900 --> 00:02:07,420
samat yksinkertainen, loistava oivallukset ovat mitä aiot antaa meille

38
00:02:07,420 --> 00:02:10,259
ratkaista paljon monimutkaisempi ja enemmän mielenkiintoisia ongelmia,

39
00:02:10,259 --> 00:02:12,930
joukossa joitakin asioita itsestäänselvyyksinä jo näinä päivinä.

40
00:02:12,930 --> 00:02:15,720
Miljardeille verkkosivuille siellä, ja silti Google ja Bing ja vastaavat

41
00:02:15,720 --> 00:02:17,660
pystyvät löytämään asioita meille tuollaista.

42
00:02:17,660 --> 00:02:22,300
Se ei tapahdu käyttämällä lineaarista hakua hakemalla kaikki mahdolliset verkkosivuja.

43
00:02:22,300 --> 00:02:25,290
Facebook voi kertoa kuka kaikki ystäväsi ovat tai ystävien,

44
00:02:25,290 --> 00:02:28,250
ja sekin voidaan tehdä näennäisesti hetkessä näinä päivinä

45
00:02:28,250 --> 00:02:30,820
vaikka heillä on miljoonia käyttäjiä.

46
00:02:30,820 --> 00:02:34,250
>> Ja niin miten todella ratkaisemaan ongelmia, jotka mittakaavassa lopulta vähentää

47
00:02:34,250 --> 00:02:37,830
ajatuksiin me katsoimme viikolla 0 ja hieman tänään.

48
00:02:37,830 --> 00:02:42,320
Emme uudelleen suorittaa tämän algoritmi, mutta muistuttaa teimme myös viikolla 0 tämän harjoituksen

49
00:02:42,320 --> 00:02:44,780
missä olimme kaikki seisomaan, ottaa numero 1,

50
00:02:44,780 --> 00:02:48,720
ja sitten meillä oli kaikki itsensä count pariksi pois, lisäämällä numerot yhteen,

51
00:02:48,720 --> 00:02:51,930
Sitten puolet jengi istui joka iteraation.

52
00:02:51,930 --> 00:02:56,750
Menimme 500 opiskelijaa 250-125 ja niin edelleen.

53
00:02:56,750 --> 00:03:00,080
Mutta kuten sanoimme maanantaina, voimakas ajatus siellä

54
00:03:00,080 --> 00:03:02,460
oli se, että jos me kaksinkertaistunut koko ongelman

55
00:03:02,460 --> 00:03:06,480
ja kaikki lapsia Justice tai EY 10 tuli takaisin huoneeseen ja liittyi meihin,

56
00:03:06,480 --> 00:03:09,510
No, voisimme ehkä laskea, että koko yhteenlaskettu ryhmän

57
00:03:09,510 --> 00:03:13,380
vain 1 enemmän suuria iterointia silmukan koska ne olisivat vain ehkä kaksinkertaiseksi

58
00:03:13,380 --> 00:03:15,630
tai EC 10 tapauksessa hieman yli kaksinkertainen koko.

59
00:03:15,630 --> 00:03:18,440
Ja niin meillä olisi viettää vähän enemmän aikaa,

60
00:03:18,440 --> 00:03:22,000
mutta meidän ei tarvitse viettää 400 tai 700 enemmän vaiheita.

61
00:03:22,000 --> 00:03:26,550
>> Vain maalata tätä kuvaa tavalla, joka on hieman vähemmän abstrakti, älkäämme ovat kaikki seisomaan.

62
00:03:26,550 --> 00:03:31,100
Mutta jos ne teistä, jotka päättivät istua orkesterin tänään panisi pahakseni seisomaan,

63
00:03:31,100 --> 00:03:34,580
Katsotaan jos voimme selvittää teistä, jotka korkein henkilö on

64
00:03:34,580 --> 00:03:36,730
tekemällä samanlaista vertailevan algoritmin.

65
00:03:36,730 --> 00:03:41,830
Joten jos olet istuu orkesteri, anteeksi, mutta askel 1, stand up;

66
00:03:41,830 --> 00:03:44,650
vaihe 2, paria pois kenenkään lähellä sinua,

67
00:03:44,650 --> 00:03:49,360
selvittää kuka on pitempi, ja istua alas, jos olet lyhyempi.

68
00:03:49,360 --> 00:03:51,360
Toista sitten.

69
00:03:51,360 --> 00:03:56,280
[Opiskelijat sorinaa]

70
00:04:13,450 --> 00:04:15,320
>> Okei.

71
00:04:15,320 --> 00:04:19,010
Okei. Yksi jää pystyyn. Mikä sinun nimesi on? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, olet korkein henkilö orkesterissa osiossa tänään.

73
00:04:21,959 --> 00:04:28,100
>> Onnittelut. [Aplodit ja hurraa] Okei. On istuin. Joten löysimme Andrew.

74
00:04:28,100 --> 00:04:30,870
Mutta kuinka kauan se olisi ottanut minua esimerkiksi löytää Andrew

75
00:04:30,870 --> 00:04:33,740
Tässä orkesteri osassa 50 + tai niin ihmiset?

76
00:04:33,740 --> 00:04:36,900
Olisin voinut ottaa melko yksinkertainen lähestymistapa ja aloita täältä.

77
00:04:36,900 --> 00:04:39,270
Ja olen 2 henkilöä seisomaan ja minä vain vertailla niitä,

78
00:04:39,270 --> 00:04:42,120
ja sitten sanon kuka on hieman lyhyempi, "Okei, istut alas,"

79
00:04:42,120 --> 00:04:44,380
ja aion muistaa kuka pitempi henkilö oli.

80
00:04:44,380 --> 00:04:49,030
Sitten toistan, toistan, toistan, ja minä roikkua kiinni korkein henkilö

81
00:04:49,030 --> 00:04:51,920
kunnes löydän jonkun hieman pitempi kuin niitä, jolloin

82
00:04:51,920 --> 00:04:54,950
hieman lyhyempi henkilö on istuutua.

83
00:04:54,950 --> 00:04:57,690
Mutta että algoritmi tämän orkesterin osassa, jos on n sinusta,

84
00:04:57,690 --> 00:05:00,480
kuinka monta askelta on, että algoritmi vie? >> [Opiskelija] N.

85
00:05:00,480 --> 00:05:03,580
>> Se vie n, oikealle, koska pahimmassa tapauksessa, niin sanotusti,

86
00:05:03,580 --> 00:05:09,090
korkein henkilö on viimeinen henkilö, että saan vain satunnaisesti huonoa onnea.

87
00:05:09,090 --> 00:05:14,260
Joten pahimmassa tapauksessa käyntiaika, että algoritmi on lineaarinen, se on n,

88
00:05:14,260 --> 00:05:18,070
jossa n on koko joukko ihmisiä tilassa, koko ongelmaa.

89
00:05:18,070 --> 00:05:19,600
Mitä tästä algoritmi?

90
00:05:19,600 --> 00:05:22,080
Se, että te kaikki nousivat seisomaan ja sitten taas puolet istuit alas,

91
00:05:22,080 --> 00:05:23,950
puolet istuit alas, puolet istuit alas.

92
00:05:23,950 --> 00:05:26,070
Kuinka monta askelta on, että on ryhdyttävä, jos siellä n. teistä täällä?

93
00:05:26,070 --> 00:05:30,200
[Opiskelija] N log n. >> Se olisi huonompi. Log n.

94
00:05:30,200 --> 00:05:32,930
>> Joten log n, vaikka et ihan muista mitä logaritmi on,

95
00:05:32,930 --> 00:05:38,410
nyt, vain ymmärtää, että se liittyy jotenkin tähän puolittaa ja puolittaa ja puolittaa.

96
00:05:38,410 --> 00:05:41,000
Se ei tarvitse olla tekijä, 2. Se voisi olla tekijä 3.

97
00:05:41,000 --> 00:05:46,560
Mutta se on tämän samojen sellainen tekijä, että koko ongelman alkaa tästä

98
00:05:46,560 --> 00:05:49,620
mutta sitten heti menee tässä, niin tässä, niin tässä, niin tässä.

99
00:05:49,620 --> 00:05:53,580
Et ota pieniä puree pois ongelman, olet todella hakkaamalla pois sitä

100
00:05:53,580 --> 00:05:56,160
isolla iskulla kerta.

101
00:05:56,160 --> 00:06:00,810
Joten meillä oli 50 ihmistä, sitten 25, sitten 12 ½ tai 13 ihmistä seisoo,

102
00:06:00,810 --> 00:06:05,370
Sitten 6 ½ ja niin edelleen, kunnes lopulta vain Andrew jäi seisomaan.

103
00:06:05,370 --> 00:06:08,710
Joten aiomme soittaa että log n, ja voit visualisoida tämän seuraavasti.

104
00:06:08,710 --> 00:06:12,570
Recall Kuvan täällä missä lineaarinen algoritmi on kuin punainen viiva siellä,

105
00:06:12,570 --> 00:06:17,520
keltainen viiva oli laskenta by 2s algoritmi, jota käytimme laskemista opiskelijoille

106
00:06:17,520 --> 00:06:22,300
aikaisemmin, mutta tänään pyhä Graal aikoo pysyä tämän vihreän linjan

107
00:06:22,300 --> 00:06:25,470
jos jos kaksinkertaistui ihmisten määrä orkesterin osassa tai vain sanoi,

108
00:06:25,470 --> 00:06:29,170
helvetti, nyt on kaikille koko huoneeseen seisomaan, ei niin iso juttu

109
00:06:29,170 --> 00:06:31,560
koska suunnilleen kaksinkertaistaa kuinka monet ihmiset ovat täällä,

110
00:06:31,560 --> 00:06:33,500
1 lisää iteraatio, ei ole ongelma.

111
00:06:33,500 --> 00:06:36,200
>> Olemme huomanneet Andrew tai kuka sattuu olemaan pitempi kuin Andrew

112
00:06:36,200 --> 00:06:38,770
on mezzanine tai parvekkeella.

113
00:06:38,770 --> 00:06:42,140
Joten tämä yksinkertainen ajatus, että teimme paljon itsestäänselvyytenä puhelinluettelosta,

114
00:06:42,140 --> 00:06:46,170
ymmärtää, että on olemassa niin monia erilaisia ​​paikkoja, joissa voimme soveltaa sitä.

115
00:06:46,170 --> 00:06:50,810
Vain lyödä joitakin ammattikieltä - oikeastaan ​​pikemminkin kuin ammattikieltä ensin

116
00:06:50,810 --> 00:06:52,750
anna minun mennä tätä kuvaa tänne.

117
00:06:52,750 --> 00:06:56,970
Juuri nyt puhuimme n ja n / 2 ja kirjaudu sitten N,

118
00:06:56,970 --> 00:07:00,500
mutta voimme varmasti keksiä, koska me aikana lukukauden,

119
00:07:00,500 --> 00:07:05,130
muitakaan matemaattisia kaavoja kuvaamaan tätä yleistä käsitettä ajoaikaan.

120
00:07:05,130 --> 00:07:07,580
Nämä ovat asiayhteydestään nyt, koska näemme ennen pitkää

121
00:07:07,580 --> 00:07:09,900
algoritmeja että nämä todella ovat.

122
00:07:09,900 --> 00:07:17,990
>> Mutta huomaa täällä lineaarinen viiva n, suora, on oikeastaan ​​hyvin vähän osoittaa juuri nyt.

123
00:07:17,990 --> 00:07:22,950
Se on eräänlainen optinen harha, että me vain muuttaa mitä x-akseli edustaa

124
00:07:22,950 --> 00:07:26,130
ja y-akseli, ja voimme tehdä suoran pisteen mihin suuntaan tahansa haluamme.

125
00:07:26,130 --> 00:07:30,350
Mutta syy, että se on niin näennäisesti tasainen nyt

126
00:07:30,350 --> 00:07:35,690
on, koska tarvitsimme tehdä tilaa tätä kuvaajaa paljon hitaammin käyntiaikoja.

127
00:07:35,690 --> 00:07:39,030
Nyt tiedämme, että on olemassa joitakin melko huonoja algoritmeja elämässä,

128
00:07:39,030 --> 00:07:43,790
joista osa ei oteta n toimiin tai, vielä parempaa, log n toimia, mutta enemmän.

129
00:07:43,790 --> 00:07:48,820
Joten yläpuolelle n täällä alaosassa huomautus siellä n kertaa log n,

130
00:07:48,820 --> 00:07:51,410
ja näemme, mitä tämä tarkoittaa ennen pitkää.

131
00:07:51,410 --> 00:07:56,010
Yläpuolella on n potenssiin, ja emme ole nähneet mitään n potenssiin algoritmit vielä, mutta olemme aikeissa.

132
00:07:56,010 --> 00:07:57,660
Ja se näyttää todella pahalta.

133
00:07:57,660 --> 00:08:01,610
On 2 n, jotain eksponentiaalinen, joka tuntuu vieläkin pahempi.

134
00:08:01,610 --> 00:08:05,760
Ja vielä, kumma kyllä, sitten on n kuutioitu, jotka, jos olet tavallaan ajatellen,

135
00:08:05,760 --> 00:08:10,000
jos sellainen tehdä matematiikkaa, 2 n todella tulee paljon suorempi,

136
00:08:10,000 --> 00:08:15,930
huomattavasti ylempänä kuin n kuutioitu jos tarkastellaan akselit tarpeeksi pitkälle ulos.

137
00:08:15,930 --> 00:08:19,890
Joten huomaa nyt nämä akselit ovat mielivaltaisesti 2-10 x-akselilla.

138
00:08:19,890 --> 00:08:21,770
>> Ja mitä se tarkoittaa?

139
00:08:21,770 --> 00:08:23,890
Tämä tarkoittaa 2 henkilöä 10 henkilöä huoneessa.

140
00:08:23,890 --> 00:08:27,200
Siinä kaikki x keinoin: koko ongelma, mitä konteksti on.

141
00:08:27,200 --> 00:08:30,420
Ja pystyakseli nyt on monta sekuntia tai useita vaiheita -

142
00:08:30,420 --> 00:08:31,840
Joissakin aikayksikössä.

143
00:08:31,840 --> 00:08:34,740
Mutta huomaa, että se on 0-60 ja 0-10.

144
00:08:34,740 --> 00:08:38,549
Mutta jos me tavallaan loitontaa, kuten ehkä Excelissä tai jotkut kartoitus ohjelmisto,

145
00:08:38,549 --> 00:08:43,370
ja menemme jopa 200000, huomaat, että jotain 2-N

146
00:08:43,370 --> 00:08:47,520
on menossa kokonaan hukuttaa käyntiaikoja n potenssiin,

147
00:08:47,520 --> 00:08:50,960
n kuutioitu n log n - kaikki olemme puhuneet toistaiseksi.

148
00:08:50,960 --> 00:08:54,190
Ja silti saalis on, kun aletaan puhua asioista, kuten Facebook

149
00:08:54,190 --> 00:08:57,150
missä olet monia, monia, monia ihmisiä kaikki toisiinsa,

150
00:08:57,150 --> 00:09:00,650
Sinulla on n ihmistä, joista kukin voi olla niin monta kuin n kanssa

151
00:09:00,650 --> 00:09:02,860
jos kaikki on eräänlainen kaveri-kaveri maailmassa,

152
00:09:02,860 --> 00:09:08,100
No, se on n kertaa n jo, joten on n: n potenssiin mahdollista ystävyyssuhteita,

153
00:09:08,100 --> 00:09:10,950
ainakin 1 suuntaan, N neliö mahdollista ystävyyssuhteita.

154
00:09:10,950 --> 00:09:15,330
Niin, että jo nyt, että etsimällä Facebook sosiaalinen kuvaaja, niin sanotusti,

155
00:09:15,330 --> 00:09:18,090
voi aloittaa ilmaistaan ​​tällaisia ​​kaavoja.

156
00:09:18,090 --> 00:09:19,820
>> Palaamme ja tekevät paljon konkreettisempaa,

157
00:09:19,820 --> 00:09:23,280
mutta nyt tavoite seuraavalle monta viikkoa

158
00:09:23,280 --> 00:09:27,170
tulee olemaan varmasti ei edetä toteuttamisessa algoritmeja tai koodi

159
00:09:27,170 --> 00:09:29,870
että päätyvät ottaen niin paljon aikaa kuin jotain tällaista.

160
00:09:29,870 --> 00:09:33,110
Mutta kiehtova juttu tietojenkäsittelytiede jos jatkaa tällä alalla

161
00:09:33,110 --> 00:09:38,320
ottaen luokkia kuten CS121, CS124, jotka molemmat ovat teoriassa kursseja,

162
00:09:38,320 --> 00:09:41,300
on, että itse asiassa joitakin ongelmia, joita tässä maailmassa

163
00:09:41,300 --> 00:09:45,710
että pohjimmiltaan, sikäli kuin tiedämme, ei voida ratkaista yhtään nopeammin

164
00:09:45,710 --> 00:09:48,880
kuin pahin nämä kuvaajat todella ehdottaa.

165
00:09:48,880 --> 00:09:53,660
Joten siellä paljon avoimia ongelmia tässä maailmassa tehdä paljon paremmin kuin ihmisillä on toistaiseksi.

166
00:09:53,660 --> 00:09:56,130
>> Joten aloitetaan sitten tämän esimerkin.

167
00:09:56,130 --> 00:09:59,650
Näimme Sean kamppailevat tämän kameran, aivan liian hankalasti videon.

168
00:09:59,650 --> 00:10:05,270
Mutta todellisuus oli kun Sean pyrki löytämään taululle näin numero 7,

169
00:10:05,270 --> 00:10:10,300
Muistutan, että olen sanonut, että "On jossain takana paperinpaloja tai valkoiset ovet

170
00:10:10,300 --> 00:10:12,570
"Numero 7. Sean, löytää se meille."

171
00:10:12,570 --> 00:10:14,200
Ja se oli ihanan hankala katsella

172
00:10:14,200 --> 00:10:15,790
koska hän oli todella kamppailevat tämän ongelman kanssa.

173
00:10:15,790 --> 00:10:19,720
Mutta todellisuus oli Sean tekivät samoin kuin kuka tahansa huoneeseen olisi voinut tehdä.

174
00:10:19,720 --> 00:10:21,890
Hän otti hieman kauemmin kuin tavallinen ihminen voi olla,

175
00:10:21,890 --> 00:10:24,760
mutta hän olettaa, että siellä oli joitakin temppu tähän ongelmaan,

176
00:10:24,760 --> 00:10:26,590
Hän olettaa, että hän puuttuu jotain.

177
00:10:26,590 --> 00:10:29,320
Ja se ei auta, että sadat silmät otetaan alas häneen.

178
00:10:29,320 --> 00:10:34,250
>> Mutta todellisuus oli, jos tulo ongelma on joukko satunnaisia ​​numeroita

179
00:10:34,250 --> 00:10:37,120
ja sinua pyydetään löytämään 1 sellainen määrä,

180
00:10:37,120 --> 00:10:39,770
parasta mitä voi tehdä on lineaarinen haku.

181
00:10:39,770 --> 00:10:44,060
Aloita vasemmalta, siirry oikealle tai aloita oikealla, siirrä vasemmalle.

182
00:10:44,060 --> 00:10:48,300
Takautuvasti, saatamme ajatella, "Sean, mikset vain aloittaa toisesta päästä?"

183
00:10:48,300 --> 00:10:52,120
No, 7 voinut yhtä hyvin ollut täällä satunnaisesti,

184
00:10:52,120 --> 00:10:54,980
mutta en tietoisesti laittaa sen sinne, koska en tajunnut hän ei aio aloittaa lopussa.

185
00:10:54,980 --> 00:10:59,320
Joten minä tavallaan käsitellä tilannetta, vaan Sattumiin 7 voinut missään.

186
00:10:59,320 --> 00:11:02,380
Joten alkaen oikeasta päästä olisi ollut parempi silloin,

187
00:11:02,380 --> 00:11:04,320
mutta mitä jos ensi vuonna muutan 7 muualle?

188
00:11:04,320 --> 00:11:06,830
Se ei pohjimmiltaan uusi ratkaisu ongelmaan -

189
00:11:06,830 --> 00:11:10,520
alkaen 1 loppu tai muu - kun olet antanut muita oletuksia.

190
00:11:10,520 --> 00:11:13,620
Joten Sean aloitti katsomalla numeroita ja hän sanoi: "5. Se ei ole täällä."

191
00:11:13,620 --> 00:11:17,280
Sitten hän meni täällä ja näki 19, sitten hän pysähtyi noin 20 sekuntia,

192
00:11:17,280 --> 00:11:22,330
Sitten hän avasi 13, ja sitten kävi ilmi

193
00:11:22,330 --> 00:11:24,270
että ei näytä olevan kuvion täällä.

194
00:11:24,270 --> 00:11:28,090
Se ei ollut 1, 2, 3, 4 tai vastaava. Siellä oli aukkoja numeroita, joita ei ole apua.

195
00:11:28,090 --> 00:11:32,320
Ja myös, että käytin näitä halpoja paperinpaloja peitellä numerot

196
00:11:32,320 --> 00:11:35,270
on todella tahallinen, sillä jos olen poistanut kaikki nämä paperinpaloja,

197
00:11:35,270 --> 00:11:38,760
useimmat meistä, Sean mukana, luultavasti olisi vilkaisi eräänlainen makroskooppisesti

198
00:11:38,760 --> 00:11:43,410
klo liitutaulu ja sanoi: "Voi, 7 on tietysti oikeassa." Me teimme sen heti.

199
00:11:43,410 --> 00:11:46,460
>> Ja että voisi olla tapa ihmisen aivot toimii jossain määrin,

200
00:11:46,460 --> 00:11:50,730
mutta todellisuudessa hänen silmänsä tai mielessä oli todennäköisesti kuorimalla numerot oikealta vasemmalle,

201
00:11:50,730 --> 00:11:55,190
vasemmalta oikealle, keskelle on out - jotain oli tekeillä fysiologisesti

202
00:11:55,190 --> 00:11:57,640
sellainen, että tuntui kuin se tapahtui hetkessä,

203
00:11:57,640 --> 00:12:01,360
mutta kertoimet ovat jopa sisäisesti siellä oli jonkinlainen menetelmien löytämiseksi 7.

204
00:12:01,360 --> 00:12:05,160
Ja todellakin, nyt kun puhumme paneelit ja tietorakenteet

205
00:12:05,160 --> 00:12:08,780
ja muisti sisällä tietokoneen, ainoa asia meidän ihmisten tehdä

206
00:12:08,780 --> 00:12:13,070
on tarkastella yksittäisten muistipaikkojen 1 kerrallaan.

207
00:12:13,070 --> 00:12:16,600
>> Joten jokainen muu paikka voisi yhtä hyvin kuulua jopa joidenkin paperinpala

208
00:12:16,600 --> 00:12:21,170
koska emme voi nähdä sitä muutenkaan. Voimme vain tehdä 1 asia kerrallaan.

209
00:12:21,170 --> 00:12:25,030
Eli tässä tapauksessa Sean tapauksessa, menimme täällä ja sitten menimme täällä

210
00:12:25,030 --> 00:12:31,040
ja sitten menimme täällä, täällä, täällä, täällä, mutta taitava loppuun mennessä

211
00:12:31,040 --> 00:12:34,450
ja juuri sellainen väliin tämän yhden mielivaltaisesti löytyi 7 siellä.

212
00:12:34,450 --> 00:12:37,470
Tämä yksi ei ollut erityisen erityinen. Sekin oli epäkunnossa.

213
00:12:37,470 --> 00:12:39,530
Mutta hän viimein löytyi 7.

214
00:12:39,530 --> 00:12:45,360
Mutta nyt takeaway todellakin on, että parasta mitä voi tehdä, kun antaa mitään tietoja

215
00:12:45,360 --> 00:12:50,400
muut kuin satunnaisesti lajitella numeroita on aloittaa vasemmalle tai aloita oikealta.

216
00:12:50,400 --> 00:12:54,950
Tai pahus, voit satunnaisesti avata ovia, mutta silloinkin mitä se tarkoittaa olla satunnaisia?

217
00:12:54,950 --> 00:12:57,220
No, meillä olisi jotenkin virallistaa mitä se tarkoittaa aloittaa täällä,

218
00:12:57,220 --> 00:13:01,150
sitten mennä tänne, mene sitten tänne. Sean hienosti, ja se oli vain hauska katsella.

219
00:13:01,150 --> 00:13:06,340
Mitä jos vaan muutamme ongelman hieman ja tuoda esille tämän vuoden Sean, jos tulee?

220
00:13:06,340 --> 00:13:09,460
Olisiko kukaan olla mukava tulossa lavalle ja ratkaisemiseen hieman erilainen ongelma

221
00:13:09,460 --> 00:13:12,330
ja näkyä kamera?

222
00:13:12,330 --> 00:13:15,720
>> Mennään pidemmälle orkesteri, koska te olette ollut täysin mukana jo tänään.

223
00:13:15,720 --> 00:13:21,430
Entä vaaleanpunainen, vuonna hattu? Tule alas. Mikä on nimesi? >> Alex. >> Alex. Okei.

224
00:13:21,430 --> 00:13:24,580
Joten Alex tulee tämän vuoden Sean ja ilmestyy seuraavan useita vuosia

225
00:13:24,580 --> 00:13:27,770
arvoinen CS50 luentoja.

226
00:13:27,770 --> 00:13:30,340
Alex, nice to meet you. >> Hauska tavata myös.

227
00:13:30,340 --> 00:13:33,470
Haasteena käsillä teille on, että sinulla on se hieman helpompaa

228
00:13:33,470 --> 00:13:38,950
että kerron teille samat numerot ovat täällä, mutta nyt ne lajitellaan.

229
00:13:38,950 --> 00:13:41,800
Joten nyt sinun tehtäväsi on löytää numero 7.

230
00:13:41,800 --> 00:13:45,370
Ja itse asiassa, meidän pitäisi todella tehdä tämän - Eipä tällaista huijausta, kuten tietokone ei,

231
00:13:45,370 --> 00:13:47,990
katsomalla, mitä numerot olivat hetki sitten.

232
00:13:47,990 --> 00:13:50,360
Liidulla tämä todellisuudessa ei auta kovin paljon,

233
00:13:50,360 --> 00:13:52,810
mutta älkäämme teeskennellä, että et tiedä mitä alkuperäinen matriisi on.

234
00:13:52,810 --> 00:13:56,600
Kaikki te tiedätte nyt, että sinulla on joukko lajiteltu numerot

235
00:13:56,600 --> 00:14:00,360
että voi olla aukkoja välillä, ja sinun tehtäväsi on löytää numero 7.

236
00:14:00,360 --> 00:14:05,080
Miten, kohtuullinen ihminen, mene noin löytää numero 7?

237
00:14:05,080 --> 00:14:07,770
>> Siirry pienestä suureen? >> Okei. Siirry pienimmästä suurimpaan.

238
00:14:07,770 --> 00:14:10,990
Ja älä revi niitä pois. Toivotaan vain nostaa ne ylös, jotta voimme käyttää niitä uudelleen.

239
00:14:10,990 --> 00:14:14,730
Okei, niin 1. Odota. Ennen kuin jatkakaa, joka oli 1, selvästi väärä.

240
00:14:14,730 --> 00:14:17,270
Joten mitä mielesi läpi seuraavaksi? Mitä seuraavaksi?

241
00:14:17,270 --> 00:14:23,250
Seuraava. >> Okei. Seuraava. Hyvä. 3, joten virheellinen. Mitä seuraavaksi?

242
00:14:23,250 --> 00:14:27,670
Pitää käynnissä. >> Selvä. Pitää käynnissä. 5.

243
00:14:27,670 --> 00:14:31,110
Joten pitää käynnissä, ja haluan ojentaa sinulle tämän jälkipolville.

244
00:14:31,110 --> 00:14:35,720
7. >> Erinomainen. Erittäin hyvä. Löytyi numero 7. [Aplodit]

245
00:14:35,720 --> 00:14:39,720
Joten se oli hyvä, mutta Sean liian löytynyt numero 7.

246
00:14:39,720 --> 00:14:44,490
Ja väitän, että et ole oikeasti hyödyntää tätä ylimääräistä tieto,

247
00:14:44,490 --> 00:14:47,780
joka on, että nämä luvut on lajiteltu.

248
00:14:47,780 --> 00:14:51,520
Joten me voisimme tehdä paremmin? Kaikki ehdotukset tänne? Niin, takaisin.

249
00:14:51,520 --> 00:14:54,710
[Opiskelija] Binary search. >> Minulla ei ole aavistustakaan, mitä binäärihakupuu on.

250
00:14:54,710 --> 00:14:58,030
>> [Opiskelija] Aloita keskellä. >> Aloita keskellä. Okei. Joten katsotaanpas jos saamme sinne.

251
00:14:58,030 --> 00:15:02,580
Joten jos vaan käsketään alkavat keskeltä, mennä eteenpäin ja avata keskiovesta.

252
00:15:02,580 --> 00:15:04,580
On 8 heistä, joten olet menossa on mielivaltaisesti valita yhden

253
00:15:04,580 --> 00:15:09,800
hieman vasemmalle tai oikealle. Okei. 7! [Aplodit] Very nice.

254
00:15:09,800 --> 00:15:11,410
Okei, mutta minne olimme menossa tähän?

255
00:15:11,410 --> 00:15:14,990
Oletetaan vain murtaa tie aloitit täällä

256
00:15:14,990 --> 00:15:16,670
koska yhtä voinut tapahtua yhtä hyvin.

257
00:15:16,670 --> 00:15:19,540
Me vain sattui tietämään että 7 oli siellä. Tämä on siis 13.

258
00:15:19,540 --> 00:15:21,980
Joten jos he lajitellaan ja me vain alkoi keskellä,

259
00:15:21,980 --> 00:15:24,600
mitä optimaalinen seuraavaksi on?

260
00:15:24,600 --> 00:15:27,740
Mene vasemmalle. Ja niin tässä tulee puhelinluettelon esimerkki uudelleen.

261
00:15:27,740 --> 00:15:30,130
Jos 13 on täällä ja me tiedämme lajitellaan,

262
00:15:30,130 --> 00:15:33,900
Sitten kaikki nämä palaset paperin mielenkiinnoton meille nyt

263
00:15:33,900 --> 00:15:37,400
koska me tiedämme jo, että 7 on vasemmalla

264
00:15:37,400 --> 00:15:39,510
Jos nämä numerot lajitellaan ja löysimme 13.

265
00:15:39,510 --> 00:15:42,500
>> Joten mitä sinun seuraavaksi täällä? >> Mene vasemmalle. >> Okei, hyvä.

266
00:15:42,500 --> 00:15:45,080
Joten mene vasemmalle, ja - odota, hei, hei, hei. Se pettää.

267
00:15:47,140 --> 00:15:51,350
Joten olet löytänyt 7, mutta mitä algoritmia me juuri sovellettu?

268
00:15:51,350 --> 00:15:56,450
Aloita keskellä. >> Hyvä. Joten mitä looginen jatke saman idean?

269
00:15:56,450 --> 00:15:58,970
Voi vain nämä. >> Aivan. >> Joten aloitan täällä. >> Hyvä.

270
00:15:58,970 --> 00:16:02,020
Joten nyt mentiin hieman vasemmalle uudelleen. Se on 3.

271
00:16:02,020 --> 00:16:05,310
Mutta mielenkiintoinen takeaway nyt kumpi teillä ei tarvitse välittää?

272
00:16:05,310 --> 00:16:08,040
Nämä 2. >> Nämä 2. Joten nyt tämä voi mennä pois, tämä voi mennä pois.

273
00:16:08,040 --> 00:16:12,330
Nyt ongelma oli 8 silloin oli koko 4 on nyt koko 2.

274
00:16:12,330 --> 00:16:16,430
Saamme melko lähellä. Jälleen, mene keskelle näiden 2 elementtiä.

275
00:16:16,430 --> 00:16:20,430
>> Okei. Joten se on tavallaan valitettavaa, että nyt olemme aina menossa vasemmalle, koska olemme pyöristäminen alaspäin.

276
00:16:20,430 --> 00:16:25,150
Mutta se on hienoa, koska nyt meillä heittää tämän pois ja kaikesta muusta, jättäen meille vain 7.

277
00:16:25,150 --> 00:16:30,490
Annetaan aplodit. Löysimme 7 uudelleen. [Aplodit] Okei. Toki.

278
00:16:30,490 --> 00:16:32,220
Odota vain 1 sekunti.

279
00:16:32,220 --> 00:16:36,630
Vaikka tämä seuraava prosessi sellainen kesti hieman kauemmin kuin se tuntui,

280
00:16:36,630 --> 00:16:40,150
rehellisesti, ensimmäinen vaistojen paras, eikö? Löysimme 7 välittömästi.

281
00:16:40,150 --> 00:16:46,740
Mutta olisimme löytäneet 7 nopeammin, ei väliä mitä, tässä esimerkissä verrattuna tämä

282
00:16:46,740 --> 00:16:50,100
koska jos kaikki numerot ovat lajitellaan, aivan kuten sivujen puhelinluettelosta,

283
00:16:50,100 --> 00:16:54,580
voit todellakin pilkkoa puolet ongelmasta ulos uudestaan ​​ja uudestaan ​​ja uudestaan.

284
00:16:54,580 --> 00:16:56,740
Ja se ei ole aivan niin helppoa nähdä tämä vain 8 numeroa

285
00:16:56,740 --> 00:17:00,100
toisin kuin 1000-sivun puhelinluettelon, jossa olet todella nähdä sen visuaalisesti,

286
00:17:00,100 --> 00:17:03,120
mutta tässä tapauksessa tänne, kun Sean oli etsimässä 7,

287
00:17:03,120 --> 00:17:06,020
kuinka monta askelta pahimmassa tapauksessa se olisi ottanut hänet? >> [Opiskelija] 7.

288
00:17:06,020 --> 00:17:11,670
7 pahimmassa tapauksessa. No, pahimmassa tapauksessa 7 jos siellä 8 ovia täällä.

289
00:17:11,670 --> 00:17:13,440
Se olisi vienyt hänet 8 askelmaa.

290
00:17:13,440 --> 00:17:18,170
>> Joten jos siellä on n ovia, se olisi voinut Sean pari vuotta sitten n askelta.

291
00:17:18,170 --> 00:17:21,520
Nyt sinun tapauksessasi, Alex, sillä nämä luvut lajitellaan -

292
00:17:21,520 --> 00:17:25,130
ja voimme sellaista päättelevät tästä, josta olemme olleet toistaiseksi tämän tarinan -

293
00:17:25,130 --> 00:17:28,300
mitä käyntiaika Alexin enemmän älykäs algoritmi

294
00:17:28,300 --> 00:17:30,770
ja aloittaen keskeltä ja sitten toistamalla?

295
00:17:30,770 --> 00:17:36,490
[Opiskelija] 3. >> Joten se tulee olemaan 3, karkeasti, jos menet 8-4 to 2-1.

296
00:17:36,490 --> 00:17:40,660
Joten 3 askelta tai yleisemmin se log n uudelleen.

297
00:17:40,660 --> 00:17:43,380
Aina olet puolittamista ja puolittaminen ja puolittaa ja puolittamisen,

298
00:17:43,380 --> 00:17:45,290
se ilmaus ajatus log n.

299
00:17:45,290 --> 00:17:48,140
Ja jotta olisi kestänyt vain 3 askelta, ja se todellakin teki

300
00:17:48,140 --> 00:17:50,890
kun avasimme ovet puolittaa ja puolittaa,

301
00:17:50,890 --> 00:17:53,770
tämä olisi ottanut Sean noin 7 tai 8 vaiheita.

302
00:17:53,770 --> 00:17:56,330
Joten kiitos siitä, että meille tänä vuonna. >> Kiitos. Kiva tavata.

303
00:17:56,330 --> 00:18:00,170
Kiitos Alex. >> Samoin. [Aplodit]

304
00:18:00,170 --> 00:18:02,150
>> Mikä on sitten todellinen seuraus tästä?

305
00:18:02,150 --> 00:18:06,050
Nyt kuvitella, että se ei ole 8 ovia, jotka suoraan sanottuna kaikki voisimme löytää jotain

306
00:18:06,050 --> 00:18:10,430
takana 8 ovien melko nopeasti vain repimällä paperilappuja ja menossa meidän vaistoja.

307
00:18:10,430 --> 00:18:14,430
Mutta mitä jos se on miljoona ovet? Mitä jos se on 4000000000 ovea?

308
00:18:14,430 --> 00:18:19,630
Kun kyseessä 4000000000 ovea, olet todella menossa halua mennä Alexin algoritmi,

309
00:18:19,630 --> 00:18:23,150
binary search alamme soittaa sitä tai hajoita ja hallitse, yleisemmin,

310
00:18:23,150 --> 00:18:25,220
missä pidät puolittaa ja puolittaa ongelma,

311
00:18:25,220 --> 00:18:30,510
koska jos olet 4000000000 ovea, kuinka monta kertaa voit pilkkoa 4 miljardin puoli?

312
00:18:30,510 --> 00:18:33,870
[Opiskelija] 32. >> Se on oikeastaan ​​32. Voit työskennellä tämän ulos paperille tai pään.

313
00:18:33,870 --> 00:18:38,490
Menet 4000000000-2 miljardia to 1 miljardista puoli miljardia, 250 miljoonaa, piste, piste, piste.

314
00:18:38,490 --> 00:18:41,620
Ja jos et ulos matematiikka, aiot todellakin päästä 32,

315
00:18:41,620 --> 00:18:44,950
ja tosiasiallisesti liittyy tietojenkäsittelytieteessä, koska me yleensä lasketa toimivalta 2.

316
00:18:44,950 --> 00:18:47,600
2 32 sattuu olemaan 4000000000.

317
00:18:47,600 --> 00:18:51,440
Joten siellä paljon merkitystä tällaisia ​​valtuuksia 2 tietotekniikassa.

318
00:18:51,440 --> 00:18:55,120
>> Mutta entä 8000000000? Kuinka monta askelta on, että vie jos on 8000000000 ovia?

319
00:18:55,120 --> 00:19:00,350
[Opiskelija] 33. >> So 33. Mitä jos 16000000000 ovet? Kuinka monta askelta on joka vie?

320
00:19:00,350 --> 00:19:05,020
[Opiskelija] 34. >> 34. Voisimme tavallaan jatkaa tätä kyllästymiseen. Mutta se voimakas asia.

321
00:19:05,020 --> 00:19:09,430
Voit ottaa miljardeja enemmän tuotantopanosten ongelman, mutta ei ole iso juttu,

322
00:19:09,430 --> 00:19:14,140
te vain ottaa 1 ylimääräisen purra irti ja siten antaa meille jotain binäärihakupuu

323
00:19:14,140 --> 00:19:15,920
tai hajoita ja hallitse, yleisemmin.

324
00:19:15,920 --> 00:19:17,990
Mutta olen tavallaan pettää täällä, eikö?

325
00:19:17,990 --> 00:19:22,410
Tapauksessa Alex algoritmi, hänellä oli etulyöntiaseman Sean.

326
00:19:22,410 --> 00:19:27,780
Hän tiesi, että nämä luvut olivat lajiteltu, mutta Alex ei tarvitse lajitella niitä itse.

327
00:19:27,780 --> 00:19:30,520
Olen etukäteen tulivat taululle ja millaisia ​​varmisti

328
00:19:30,520 --> 00:19:33,670
että Piirsin ne kaikki ulos lajitellaan järjestyksessä, sitten peitti heidät paperilla.

329
00:19:33,670 --> 00:19:35,850
Mutta kuinka paljon työtä ei se ota minua?

330
00:19:35,850 --> 00:19:40,110
Jos olisimme alkoi nämä numerot joissakin näennäisesti satunnaisessa järjestyksessä -

331
00:19:40,110 --> 00:19:43,320
Tässä tapauksessa näistä yksinkertaisemmista numeroita 1: stä 8 täällä -

332
00:19:43,320 --> 00:19:46,090
Miten me edetä lajittelua näistä arvoista?

333
00:19:46,090 --> 00:19:52,530
Jos olisit ihmisen tietyn tehtävän, millaisia ​​intuitiivisen lähestymistavan otat

334
00:19:52,530 --> 00:19:54,800
lajitteluun koko joukko numeroita?

335
00:19:54,800 --> 00:19:57,050
Nämä asiat olivat vahvistetut kuin palapelin palaset. Joo.

336
00:19:57,050 --> 00:19:59,950
>> [Opiskelija] Ottaisin jokaisen numeron ja verrata sitä jokainen

337
00:19:59,950 --> 00:20:03,180
ja jatka vasemmalle. >> Okei, hyvä.

338
00:20:03,180 --> 00:20:05,720
Joten ota jokainen numero, vertaa sitä yksi sen vieressä,

339
00:20:05,720 --> 00:20:09,610
ja sitten vain pitää liikkuvat pitkin luettelon, millaisia ​​rejiggering asioita kuten mennä.

340
00:20:09,610 --> 00:20:13,800
Joten tässä meillä on mahdollisuus ehkä muutama enemmän ihmisiä sekaantua.

341
00:20:13,800 --> 00:20:16,290
Onko meillä 8 enemmän vapaaehtoisia, jotka haluaisivat keksiä?

342
00:20:16,290 --> 00:20:23,950
Hieman vähemmän paineita, koska et ole ainoa. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Tule alas. Te aiotaan numerot 1: stä 8.

344
00:20:28,190 --> 00:20:36,050
Katsotaan jos emme voi tehdä tätä lajittelu Alex pitkälti samalla tavalla tein sen etukäteen.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Menkää ja jos olisi, riviin lavalle välillä nuottiteline ja minä täällä

347
00:20:40,760 --> 00:20:44,960
samassa järjestyksessä kuin dia näytössä.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Autamme sinua seuraavassa esimerkissä. Odota, odota. Täällä mennään. Odota.

350
00:20:53,230 --> 00:20:57,570
Seuraavassa esimerkissä on nyt. Tässä mennään. Numero 8. Tule ylös.

351
00:20:57,570 --> 00:21:00,270
Selvä. Sort itsenne tämän mukaan.

352
00:21:00,270 --> 00:21:03,620
Työnnä vain hieman sivuun musiikin seistä täällä.

353
00:21:03,620 --> 00:21:12,310
Joten meillä on 4, 2, 6 - päästä sinne, tänne, tuolla - 3.

354
00:21:12,310 --> 00:21:17,570
Joo. Okei. Voit mennä tänne. Ei, sinä siellä.

355
00:21:17,570 --> 00:21:21,840
Joo, oikeassa. No olen väärässä. Tuolla. Okei, hyvä. Okei.

356
00:21:21,840 --> 00:21:24,930
Joten nyt mennään lajitella ne nousevaan järjestykseen.

357
00:21:24,930 --> 00:21:26,210
>> Miten voin mennä noin tekee näin?

358
00:21:26,210 --> 00:21:28,630
Algoritmi, joka ehdotti hetki sitten oli, miksi emme vain verrata

359
00:21:28,630 --> 00:21:31,970
ihmiset, jotka ovat tavallaan vierekkäin ja sitten korjata mahdolliset virheet,

360
00:21:31,970 --> 00:21:33,540
liikkuvat vasemmalta oikealle.

361
00:21:33,540 --> 00:21:36,580
Joten tässä meillä on 4 ja 2, ilmeisesti epäkunnossa. Mennään swap sinua. Okei.

362
00:21:36,580 --> 00:21:40,760
Joten nyt aion siirtyä ruodussa. 4 ja 6, nope. [Naurua]

363
00:21:40,760 --> 00:21:45,010
6 ja 8, melko hyvä. 8 ja 1, haluan vaihtaa kaverit. Selvä.

364
00:21:45,010 --> 00:21:48,030
Joten 8 ja 3, vaihtaa kaverit.

365
00:21:48,030 --> 00:21:52,280
8 ja 7, haluan vaihtaa kaverit. 5 ja 8, erinomainen.

366
00:21:52,280 --> 00:21:54,820
Annan teille lajiteltu luettelo.

367
00:21:54,820 --> 00:21:56,860
Selvä. Joten ei aivan.

368
00:21:56,860 --> 00:22:01,180
Mutta se on parempi koska isompi numerot - tapaukseen 8 -

369
00:22:01,180 --> 00:22:04,030
ovat eräänlainen kuplina ylös vasemmalle yli oikealle.

370
00:22:04,030 --> 00:22:08,010
Joten sain 1 niistä oikealle, mutta se tuntuu tämä ei kuitenkaan ratkaise ongelmaa.

371
00:22:08,010 --> 00:22:11,150
>> Joten mitä ehdottaisit teemme seuraavaksi? >> [Opiskelija] pitää tehdä se. >> Pidämme tehdä se.

372
00:22:11,150 --> 00:22:13,740
Ja ymmärtää, jälleen, asetamme asioita joita vain ottaa kaikki ihmiset

373
00:22:13,740 --> 00:22:17,180
tavallaan älykkäästi järjestää itse perustuu tuon kuvan,

374
00:22:17,180 --> 00:22:19,040
mutta nyt meidän on oltava paljon suunnitelmallista.

375
00:22:19,040 --> 00:22:21,510
Meidän on oltava algoritmiseen siitä ikään kuin olemme kirjoittaa koodia -

376
00:22:21,510 --> 00:22:23,520
Tässä tapauksessa sanallinen pseudokoodilla.

377
00:22:23,520 --> 00:22:26,040
Joten haluan vain kokeilla uudestaan. Tämä sujui varsin hyvin. Se ei ratkaise sitä.

378
00:22:26,040 --> 00:22:30,400
Mutta kun se Epäilen vain yrittää ja yrittää uudelleen. Joten 2 ja 4, ei auta enää.

379
00:22:30,400 --> 00:22:33,200
4 ja 6. Ah! 6 ja 1, hieman parempi nyt.

380
00:22:33,200 --> 00:22:39,740
6 ja 3, hyvä. 6 ja 7, 7 ja 5, 7 ja 8, hyvä.

381
00:22:39,740 --> 00:22:44,060
Ja tiedätkö, voin varmaan jättää 8 nyt, koska hän oli listan loppuun.

382
00:22:44,060 --> 00:22:47,250
Ehkä meidän ei tarvitse huolehtia siitä, että joku menee ohi.

383
00:22:47,250 --> 00:22:49,240
Mutta katsotaanpa, jos se on turvallinen oletus.

384
00:22:49,240 --> 00:22:52,340
Nyt lista on - pahuksen - ei lajitella. Kokeillaan uudestaan.

385
00:22:52,340 --> 00:22:56,440
Niin 2 ja 4, 4 ja 1, 4 ja 3.

386
00:22:56,440 --> 00:22:59,230
4 ja 6, hyvä. 6 ja 5, hyvä.

387
00:22:59,230 --> 00:23:04,890
6, 7 ja 8, hyvä. Mutta ilmoitus, voin vain lopettaa täällä nyt ja lopettaa täällä nyt?

388
00:23:04,890 --> 00:23:07,770
[Opiskelija] Kyllä. >> Niin?

389
00:23:07,770 --> 00:23:11,160
Mitä jos joku teistä ollut numero 9 kaikki tuonne?

390
00:23:11,160 --> 00:23:13,640
Se on lajiteltu. >> Hyvä. Se on lajiteltu ensimmäisellä kerralla.

391
00:23:13,640 --> 00:23:16,050
Hyvä. Mennään takaisin. Olemme melkein siellä.

392
00:23:16,050 --> 00:23:22,800
1 ja 2, 2 ja 3, 3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8.

393
00:23:22,800 --> 00:23:26,640
>> Olen tehnyt nyt vaan, taas, olen tietokoneella, joka voi vain tehdä, mitä olen kertonut tehdä,

394
00:23:26,640 --> 00:23:30,120
ja ainoa muistikuva on, että nyt olen itse juuri tehnyt vähän työtä.

395
00:23:30,120 --> 00:23:31,700
Jotain muuttui täällä.

396
00:23:31,700 --> 00:23:37,100
Joten en ole teknisesti vahvistaneet visuaalisesti tai algoritmisesti että luettelo on todella lajitellaan.

397
00:23:37,100 --> 00:23:40,720
Eli vain hyvä toimenpide, vain olla anaali tästä, tehdään tämä 1 enemmän aikaa.

398
00:23:40,720 --> 00:23:44,040
Joten 1 ja 2, 2 ja 3, 3 ja 4. Ja tiedättekö mitä?

399
00:23:44,040 --> 00:23:46,190
Vain hyvä toimenpide, aion seurata minun käteen tällä kertaa

400
00:23:46,190 --> 00:23:51,110
kuinka monta swap voin tehdä juuri niin, että tiedän, miten paljon työtä olen itse tehnyt.

401
00:23:51,110 --> 00:23:56,930
3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8. Ei swapit.

402
00:23:56,930 --> 00:24:00,800
Joten nyt olisin oikeutetusti idiootti tehdä tätä uudelleen

403
00:24:00,800 --> 00:24:03,330
koska jos en ole työtä kautta läpikulun ihmisille,

404
00:24:03,330 --> 00:24:06,710
sitten selvästi, että tulee tapahtumaan uudelleen, jos mikään niistä ei tavallaan satunnaisesti

405
00:24:06,710 --> 00:24:10,410
adversarially liikkuvat itse noin. Joten nyt voin lopettaa.

406
00:24:10,410 --> 00:24:15,120
Nyt kysyä, kuinka paljon työtä ei oikeastaan ​​viedä minut?

407
00:24:15,120 --> 00:24:18,260
Kuinka monta askelta ei se kestää? >> N potenssiin.

408
00:24:18,260 --> 00:24:20,400
Joo, niin n neliö. Mistä saat n potenssiin alkaen?

409
00:24:20,400 --> 00:24:22,660
Sinun täytyy tarkistaa jokaisen num -

410
00:24:22,660 --> 00:24:26,530
On n numeroita, ja sinun täytyy tarkistaa kunkin numeron kanssa muiden n numerot.

411
00:24:26,530 --> 00:24:29,030
Hyvä. >> Joten se on n: n potenssiin. >> Hyvä.

412
00:24:29,030 --> 00:24:31,060
>> Joten se tuntuu se voisi hyvinkin olla n potenssiin, eikö?

413
00:24:31,060 --> 00:24:33,820
Siellä on N näitä tyyppejä, 8 erityisesti tässä tapauksessa,

414
00:24:33,820 --> 00:24:37,590
mutta joka kerta menin läpi tämän listan olin vertaamalla ensimmäinen henkilö vastaan ​​toisen,

415
00:24:37,590 --> 00:24:39,650
Toisen kolmatta uudestaan ​​ja uudestaan ​​ja uudestaan,

416
00:24:39,650 --> 00:24:42,450
ja kun sain loppuun, mitä minä tein? I redid sen.

417
00:24:42,450 --> 00:24:46,280
Joten jos me yleistää tämä selitys, olemme on n ihmisiä

418
00:24:46,280 --> 00:24:51,090
ja olen tekemässä, tietenkin, 8 askelmaa, n askelta, aina kun menen läpi tämän algoritmin.

419
00:24:51,090 --> 00:24:56,070
Mutta kuinka monta kertaa pahimmillaan minun täytyy käydä läpi tämä luettelo ihmisistä?

420
00:24:56,070 --> 00:24:59,370
[Opiskelija] N kertaa. >> Luultavasti n, oikealle, koska pahimmassa tapauksessa,

421
00:24:59,370 --> 00:25:03,410
mikä luultavasti pahimmassa tapauksessa järjestely nämä kaverit get-go?

422
00:25:03,410 --> 00:25:06,520
Jos he täysin päinvastainen järjestys

423
00:25:06,520 --> 00:25:09,310
koska vain olettaa henkisesti, let's - Mikä on nimesi? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Okei. Joten Bowen, tule tänne hetkeksi.

425
00:25:12,510 --> 00:25:16,150
>> Oletetaan, että Bowen oli tässä alussa algoritmin,

426
00:25:16,150 --> 00:25:19,790
ja emme tiedä mitä kaikki muu on, mutta Bowen täällä, tämän algoritmin -

427
00:25:19,790 --> 00:25:23,820
ja jos haluat vain kävellä kanssani - tulee kupla ylös, niin kuin hän teki ensimmäisellä kerralla,

428
00:25:23,820 --> 00:25:25,740
aina loppuun.

429
00:25:25,740 --> 00:25:29,400
Mutta oletetaan, että henkilö vieressä Bowen oli numero 7.

430
00:25:29,400 --> 00:25:33,450
Minun täytyy mennä takaisin ja saada numero 7, mikä tarkoittaa, että minun täytyy mennä aina takaisin tänne.

431
00:25:33,450 --> 00:25:36,980
Nyt minun täytyy olla, että sama kävelylle henkilön kanssa, joka on numero 7.

432
00:25:36,980 --> 00:25:40,140
Mutta entä jos sitten numero 6 oli hänen vieressään samoin?

433
00:25:40,140 --> 00:25:42,180
Sitten minun täytyy mennä takaisin ja saat 6.

434
00:25:42,180 --> 00:25:46,490
Joten jälleen, joka iteroinnin tämän silmukan Puhun kunkin n ihmisiä,

435
00:25:46,490 --> 00:25:50,090
ja saisin tehdä n näitä kävelyretkillä varmista olen vetämällä

436
00:25:50,090 --> 00:25:53,760
kaikki suurimmat osat takaisin ja takaisin ja takaisin aivan listan loppuun.

437
00:25:53,760 --> 00:25:58,230
Joten n asioita n kertaa on vain n kertaa n tai n neliöön.

438
00:25:58,230 --> 00:26:02,050
>> Joten tässä on jo meillä algoritmi, joka ei enää n, se ei enää log n,

439
00:26:02,050 --> 00:26:04,820
se on oikeastaan ​​pahempi kuin mitä olemme tehneet aiemmin.

440
00:26:04,820 --> 00:26:09,840
Joten Alex eräänlainen onnekas, että tein kaiken työn ilmeisesti edessä hänen,

441
00:26:09,840 --> 00:26:14,690
kaikki kallista työtä, jotta hän voisi nauttia tässä binäärihakupuu algoritmi,

442
00:26:14,690 --> 00:26:16,420
joka on log n.

443
00:26:16,420 --> 00:26:18,240
Mutta tämä on sopusoinnussa maanantain teema.

444
00:26:18,240 --> 00:26:23,260
Annoimme hieman enemmän tilaa, käytimme enemmän bittejä, jotta nopeuttaa meidän käyntiaika.

445
00:26:23,260 --> 00:26:26,170
Niin paljon kuin on tämä kompromisseja aikaa ja tilaa,

446
00:26:26,170 --> 00:26:31,060
saattaa myös vain olla kompromisseja aika edessä jonkinlainen saada asioita valmiina

447
00:26:31,060 --> 00:26:35,000
ja tosiasiassa ajetaan algoritmi haku. Kokeillaan toista.

448
00:26:35,000 --> 00:26:39,050
Jos teillä ei ole mielessä vain nopeasti järjestämällä itseänne vastaamaan, että taas

449
00:26:39,050 --> 00:26:42,240
Kokeillaan jotain hieman erilaista, jos se ei ole aivan niin yksinkertainen

450
00:26:42,240 --> 00:26:45,760
koska vain korjata kaikki pareittain virheitä, mikä on erittäin intuitiivinen.

451
00:26:45,760 --> 00:26:48,150
Katsotaanpa sen sijaan olla hieman tarkoituksellista ja tehdä tämän.

452
00:26:48,150 --> 00:26:51,010
Tämäkin ehdotan on luultavasti melko intuitiivinen.

453
00:26:51,010 --> 00:26:55,070
>> Katsotaanpa valitse pienin henkilön luettelosta uudestaan ​​ja uudestaan. Joten tässä sitä mennään.

454
00:26:55,070 --> 00:26:57,350
4, olet pienin ihminen olen siis nähnyt tähän mennessä,

455
00:26:57,350 --> 00:27:00,520
joten aion henkisesti muistaa että juuri osoittamalla sinua nyt.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Unohda numero 4. Löysin juuri uuden pienin elementti tässä luettelossa.

457
00:27:05,020 --> 00:27:07,410
Aion sellaista muistaa. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Näkemiin. Joten nyt aion muistaa numero 1.

459
00:27:11,190 --> 00:27:14,790
Tiedämme, että 1 on pienin, mutta olen tietokoneella. Mitä jos 0?

460
00:27:14,790 --> 00:27:17,140
Mitä jos siellä -1? Minun täytyy jatkaa.

461
00:27:17,140 --> 00:27:20,990
Joten 3, 7, 5, nope. Okei. Niin numero 1 oli pienin.

462
00:27:20,990 --> 00:27:23,640
Saanen valitse sinut listalta - we'll go näin -

463
00:27:23,640 --> 00:27:27,760
ja laittaa te mielivaltaisesti alussa luettelosta.

464
00:27:27,760 --> 00:27:29,740
Nyt, odota hetki. Olen sellainen petetty.

465
00:27:29,740 --> 00:27:34,010
Jos nämä kaverit ovat ei luetteloa 8 henkilöä, mutta jono,

466
00:27:34,010 --> 00:27:37,050
8 paloina yhtenäistä muistia - älä viitsi tehostamalla takaisin hetkeksi?

467
00:27:37,050 --> 00:27:39,060
Ei oikeastaan ​​ole tilaa teille täällä.

468
00:27:39,060 --> 00:27:41,840
Joten miten teemme tilaa - Mikä on nimesi? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Miten teemme tilaa Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Siirrymme n, jotka ovat ennen minua. >> Okei.

471
00:27:46,760 --> 00:27:48,850
Jotta voisimme siirtyä n ihmisiä, jotka ovat ennen häntä,

472
00:27:48,850 --> 00:27:52,400
joten jos te haluatte ottaa 1 tahallinen, dramaattinen askel vasemmalle.

473
00:27:52,400 --> 00:27:57,000
He kaikki tekivät, että ääneen, mutta viime kerralla Kirjoitin koodin,

474
00:27:57,000 --> 00:27:59,740
et voi tavallaan siirtää monia asioita kerralla.

475
00:27:59,740 --> 00:28:02,450
Voisimme tehdä sen silmukan, liikkuu jokainen kerran kerrallaan.

476
00:28:02,450 --> 00:28:04,340
Joten jos te panisi pahakseni tehostamalla takaisin oikealle,

477
00:28:04,340 --> 00:28:07,230
ja Sammy, jos voisit askel taaksepäin, koska siellä on vielä sijaa teille,

478
00:28:07,230 --> 00:28:11,420
nyt tehdään tämä. Jos oli Sammy hetki sitten? Tuolla.

479
00:28:11,420 --> 00:28:16,140
Joten on aukko siellä. Joten voisit siirtyä Sammyn paikalla.

480
00:28:16,140 --> 00:28:20,580
Nyt seuraava henkilö ja nyt seuraava henkilö, nyt seuraava henkilö. Nyt meillä on tilaa Sammy.

481
00:28:20,580 --> 00:28:23,490
Nyt joku yleisöstä - että oli hyvä, että oli oikein,

482
00:28:23,490 --> 00:28:27,070
tuntui vähän aikaa - mikä on nopeampi? Joo.

483
00:28:27,070 --> 00:28:29,440
[Opiskelija] Uusi array? >> Mikä tuo on? >> [Opiskelija] Uusi array? >> Okei, hyvä.

484
00:28:29,440 --> 00:28:33,200
>> Joten sopusoinnussa tämän teeman vain kompromisseja, miksi en vain tehdä uuden taulukon

485
00:28:33,200 --> 00:28:36,570
 ja sitten Sammy on uima tilaa edessä nämä ihmiset, esimerkiksi

486
00:28:36,570 --> 00:28:39,600
ja voimme vain alkaa täyttää uuden array kokonaan. Sekin toimisi.

487
00:28:39,600 --> 00:28:42,450
Mutta en ole kiinnostuneita käyttämään enemmän tilaa tänään. Mikä on toinen lähestymistapa?

488
00:28:42,450 --> 00:28:46,630
[Opiskelija] Swap. >> Okei. Voisimme vain vaihtaa nämä 2 kaverit. Mikä sinun nimesi on?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Joten Mario, olit nyt täällä.

490
00:28:49,390 --> 00:28:52,480
Sammy, voit varmuuskopioida vain hetkeksi? Mario oli täällä.

491
00:28:52,480 --> 00:28:55,830
Meillä ei ole tilaa teille enää, joten jos et mielessä aio missä Sammy on,

492
00:28:55,830 --> 00:29:02,430
laitamme Sammy täällä, ja nyt olin sitä mieltä, että Sammyn vaihtava toiminta oli paljon nopeampaa.

493
00:29:02,430 --> 00:29:06,370
Teimme 1 operaatio vaihtaa näitä tyyppejä, tai ehkä 2 vaihtaa näitä tyyppejä,

494
00:29:06,370 --> 00:29:11,210
mutta emme tee 1, 2, 3, 4, niin että tuntuu paremmalta. Nyt, odota hetki.

495
00:29:11,210 --> 00:29:14,660
Olen sellainen tehnyt ongelma pahempi, koska numero 4 oli tavallaan lähellä alkua.

496
00:29:14,660 --> 00:29:19,470
Nyt numero 4 on hieman lähempänä tätä, mutta en todellakaan tiedä tai välitä siitä.

497
00:29:19,470 --> 00:29:23,330
Joten tämä on vain huonoa tuuria, että numero 4 on hieman kauempana sen tarkoitettu paikka.

498
00:29:23,330 --> 00:29:25,110
Joten nyt toista algoritmi.

499
00:29:25,110 --> 00:29:28,410
>> Voit kertaus, kunhan tarina oli, annoimme kävelee luetteloa

500
00:29:28,410 --> 00:29:31,130
etsii pienimmän numeroitu henkilö.

501
00:29:31,130 --> 00:29:34,530
Joten nyt tehdään se uudestaan. Meillä ei tarvitse murehtia Sammy enää.

502
00:29:34,530 --> 00:29:37,590
Voimme vain mennä tänne. Ooh! Numero 2. Se on aika pieni määrä.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Okei, hyvä.

504
00:29:41,180 --> 00:29:43,770
Ja onneksi, sattumalta, minun ei tarvitse liikkua - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie koska hän on hänen oikeassa paikassa nyt.

506
00:29:45,910 --> 00:29:48,110
Tehdään tämä uudestaan ​​ja sivuuttaa nämä 2 kaverit.

507
00:29:48,110 --> 00:29:50,460
6. Se on aika pieni määrä. Ooh! 8 on varmasti isompi.

508
00:29:50,460 --> 00:29:53,410
4. Keskitytään 4. Ooh! 3 on vielä parempi.

509
00:29:53,410 --> 00:29:58,290
7 ja 5. Joten mitä me teemme nyt - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Katsotaanpa vaihtaa hänet numero 6.

511
00:30:00,250 --> 00:30:03,570
Joten jos 6 ja 3 haluaisi vaihtaa,

512
00:30:03,570 --> 00:30:07,320
olemme nyt tavallaan saanut onnekas, että 6 on lähempänä missä hän olisi,

513
00:30:07,320 --> 00:30:10,300
mutta se on vain sattumaa täällä. Joten nyt mennä tänne.

514
00:30:10,300 --> 00:30:13,430
8 on melko pieni määrä. Ooh! 4 on pienempi.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Mitä me nyt teemme? >> Vaihda. >> Aivan.

516
00:30:17,130 --> 00:30:19,010
Joten nyt tehdään tämä tavallaan nopeammin.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Jos ei 5 mennä? Hyvä. Okei.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 saa jäädä missä hän on. Mikä sinun nimesi on? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie saa jäädä missä hän on. 7 saa - Katsotaan. 7, 8. Okei.

520
00:30:31,770 --> 00:30:35,100
Joten 7 saa asua missä hän on. Mikä sinun nimesi on? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Joten Amna saa jäädä missä hän on, ja numero 8 on jo missä hän nyt olisi.

522
00:30:39,670 --> 00:30:43,960
Okei, hyvä. Tuntuu kuin olisimme juuri työllistää itsemme täällä, tosin.

523
00:30:43,960 --> 00:30:47,440
Mikä lopulta käyntiaika tämän algoritmin?

524
00:30:47,440 --> 00:30:51,900
Jos ajattelemme nämä ihmiset ole yhtä 8 vaan n? >> Se on n..

525
00:30:51,900 --> 00:30:55,440
Se on n askelta, mutta me tarkistaa joka ikinen kerta.

526
00:30:55,440 --> 00:30:57,570
Okei. N mutta olet tarkkailun joka ikinen kerta?

527
00:30:57,570 --> 00:31:03,450
Okei, mutta jos se on n askelta, ei minun pitänyt pystyä lajittelemaan sinulle juuri menossa 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Okei, se on iso ero.

529
00:31:05,590 --> 00:31:08,050
Joten n potenssiin miksi? Mitä todella tapahtuu?

530
00:31:08,050 --> 00:31:12,130
Siellä N ihmisiä tässä luettelossa, mutta löytää pienin henkilön luetteloon

531
00:31:12,130 --> 00:31:16,200
pahimmassa tapauksessa, kuinka monta askelta minun pitäisi ottaa? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, oikealle, koska pahimmassa tapauksessa, numero 1 on aina siellä,

533
00:31:19,160 --> 00:31:20,990
joten minun täytyy mennä hakemaan hänet.

534
00:31:20,990 --> 00:31:25,500
Ja sitten kun vihdoin ymmärtää 1 oli pienin, niin se on melko nopea vaihtaa niitä.

535
00:31:25,500 --> 00:31:28,450
Mutta nyt minun täytyy aloittaa alusta ja etsiä kuka?

536
00:31:28,450 --> 00:31:31,980
Seuraavaksi pienin henkilö, joka on 2. Jossa pahimmassa tapauksessa on 2?

537
00:31:31,980 --> 00:31:34,320
Voi luoja. Se on niin tänne lopussa.

538
00:31:34,320 --> 00:31:37,000
Joten nyt olen juuri tehnyt toisen n askelta, toinen n askelta.

539
00:31:37,000 --> 00:31:41,200
Ja jos meillä n ihmisiä ja pahimmassa tapauksessa pienin ihminen on n askeleen päässä,

540
00:31:41,200 --> 00:31:45,230
se taas n kertaa n, ja niin olemme taas on n potenssiin.

541
00:31:45,230 --> 00:31:47,280
Tätä ei tunne niin hyvin.

542
00:31:47,280 --> 00:31:52,150
Ja itse asiassa jopa parhaassa tapauksessa - olettaa, että ne alkaa lajitella -

543
00:31:52,150 --> 00:31:59,080
kuinka monta askelta se kestää minun käyttää tätä algoritmia lajitella nämä n ihmiset?

544
00:31:59,080 --> 00:32:01,010
N potenssiin. >> Kuulin n potenssiin. Miksi n potenssiin?

545
00:32:01,010 --> 00:32:05,240
Koska sinulla on vielä tarkistaa joka ikinen kerta. >> Joo.

546
00:32:05,240 --> 00:32:08,060
Ja sinun täytyy vaihtaa niitä. >> Vaikka me ihmiset olemme sellainen kaikkitietävä

547
00:32:08,060 --> 00:32:10,770
siinä mielessä visuaalisesti että voimme vain sellaista nähdä tämän lajitellaan,

548
00:32:10,770 --> 00:32:12,140
tietokone ei ole niin fiksu.

549
00:32:12,140 --> 00:32:14,040
Se tulee näyttämään täällä ja täällä ja täällä,

550
00:32:14,040 --> 00:32:16,610
mutta jos se, mitä se etsii on pienin elementti,

551
00:32:16,610 --> 00:32:22,110
vain tietää, että olet löytänyt pienimmän alkion mitä järkeä? Kun olet lopussa.

552
00:32:22,110 --> 00:32:25,880
Mutta siinä vaiheessa olet vain löytänyt hetkellä pienin alkio.

553
00:32:25,880 --> 00:32:28,810
Et välttämättä tiedä mitään muuta maailman tilasta.

554
00:32:28,810 --> 00:32:30,880
Joten sinun täytyy mennä uudestaan ​​ja uudestaan ​​ja uudestaan.

555
00:32:30,880 --> 00:32:34,880
>> Joten tällä kertaa olen todella katsoa tyhmä koska olen tarkkailun, okei, 2, olet pienin,

556
00:32:34,880 --> 00:32:37,530
mutta en tiedä, että yhteensä vielä.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Okei, hyvä. 2 oli todellakin pienin.

558
00:32:41,090 --> 00:32:43,150
Nyt löytää seuraavaksi pienin. Okei.

559
00:32:43,150 --> 00:32:48,350
3, olet tällä hetkellä pienin. Katsotaanpa. 4, 5, 6, 7, 8. Okei, onnisti jälleen.

560
00:32:48,350 --> 00:32:53,170
3 oli todellakin oikeassa paikassa. Mutta aion jatkaa tätä uudestaan ​​ja uudestaan ​​ja uudestaan.

561
00:32:53,170 --> 00:32:55,990
Miten voimme tehdä koskaan niin hieman paremmin?

562
00:32:55,990 --> 00:33:00,120
Sen sijaan, että ihmiset kupla ylös pareittain pienimmästä suurimpaan

563
00:33:00,120 --> 00:33:04,350
ja sen sijaan menee edestakaisin luetteloa valitsemalla sitten pienin henkilö,

564
00:33:04,350 --> 00:33:09,780
Miksi emme sen sijaan lisätä nämä ihmiset uuden luettelon askel askeleelta?

565
00:33:09,780 --> 00:33:13,080
Kokeillaan tätä. Nyt haluaisin kutsua tätä asiaa insertion sort.

566
00:33:13,080 --> 00:33:17,250
Joten tässä me olemme täällä. Numero 1. En välitä kukaan muu tässä luettelossa.

567
00:33:17,250 --> 00:33:21,310
Oma tavoite tällä hetkellä on laittaa numero 1 alussa järjestetty luettelo.

568
00:33:21,310 --> 00:33:23,910
Ja aion ehdottaa koska minulla on vain 8 palasina muistia,

569
00:33:23,910 --> 00:33:28,670
mielivaltaisesti nyt olen seinämän välillä minun muka lajittelemattoman lista,

570
00:33:28,670 --> 00:33:32,740
ja jokainen, joka on takanani aion vaatia lajitellaan.

571
00:33:32,740 --> 00:33:34,680
Eli nyt on numero 1.

572
00:33:34,680 --> 00:33:39,240
Haluan lisätä hänet minun lajiteltu lista, joten olen juuri menossa siirtää minun seinään tänne,

573
00:33:39,240 --> 00:33:43,930
ja nyt Väitän tätä lajitellaan, luettelo on lajittelematta - ainakin sikäli kuin tiedän.

574
00:33:43,930 --> 00:33:46,070
En näe kaikkia numeroita kerralla.

575
00:33:46,070 --> 00:33:49,000
>> Nyt Satun kohtaavat numero 2. Mitä teen hänen kanssaan?

576
00:33:49,000 --> 00:33:54,380
Asetan sinut nyt osaksi järjestetty luettelo. Mutta huomaa kuinka helppoa se oli.

577
00:33:54,380 --> 00:33:59,650
Minun täytyy vain katsoa. Numero 1 on siellä. Voi tietenkin 2 menee puolelle numero 1.

578
00:33:59,650 --> 00:34:03,700
Nyt mitä teen kanssa 3? Asetan sinut järjestetty luettelo. Mutta se oli super helppo.

579
00:34:03,700 --> 00:34:07,250
Tämä on erittäin helppoa, tämä on erittäin helppoa, tämä on erittäin helppo, erittäin helppo, erittäin helppo.

580
00:34:07,250 --> 00:34:12,790
Ja nyt kaikki on lajiteltu takanani, ja kuinka monta askelta ei se kestää?

581
00:34:12,790 --> 00:34:15,620
[Opiskelijat] N. >> Niin se vain n. Meillä kävi tuuri.

582
00:34:15,620 --> 00:34:18,860
Se oli vain n miksi? >> [Opiskelija] Koska luettelo lajitellaan.

583
00:34:18,860 --> 00:34:21,630
Luettelo on jo järjestetty. Niinpä saimme onnekkaita.

584
00:34:21,630 --> 00:34:25,639
Mutta me suunniteltu algoritmi tällä kertaa, että valjaat sellaista onnea,

585
00:34:25,639 --> 00:34:29,420
että parhaassa tapauksessa se ei tuhlaa turhaa aikaa.

586
00:34:29,420 --> 00:34:31,750
Joten meillä on nyt mitä me kutsumme kupla lajittelee

587
00:34:31,750 --> 00:34:33,949
jossa ihmiset eräänlainen kupla ylös pareittain.

588
00:34:33,949 --> 00:34:38,100
Meillä on nyt valikoima lajitella jossa nyppiä pois pienin ihminen uudestaan ​​ja uudestaan.

589
00:34:38,100 --> 00:34:42,350
Ja nyt meillä on insertion sort jossa me tavallaan proaktiivisesti laittaa ihmisiä minne ne kuuluvat

590
00:34:42,350 --> 00:34:45,000
yhä lajiteltu luettelo.

591
00:34:45,000 --> 00:34:49,679
Jos voisimme, aplodit nämä kaverit täällä. [Aplodit]

592
00:34:49,679 --> 00:34:52,310
Otetaan meidän 5 minuutin tauon.

593
00:34:52,310 --> 00:34:55,139
Ja kun tulemme takaisin, me räjäyttää kaikki nämä algoritmit vedestä

594
00:34:55,139 --> 00:35:00,260
jotain parempaa. Selvä. Kiitos paljon. Voit pitää niitä matkamuistoja.

595
00:35:01,710 --> 00:35:04,330
Selvä. Olemme takaisin.

596
00:35:04,330 --> 00:35:08,420
>> Ja kertaus tosi nopeasti, meillä oli nämä 3 eri lähestymistavat lajittelu,

597
00:35:08,420 --> 00:35:13,000
idea oli päästä pisteeseen, jossa joku Alex

598
00:35:13,000 --> 00:35:16,930
voisi etsiä listan numeroita nopeammin kuin joku Sean voisi.

599
00:35:16,930 --> 00:35:19,830
Ja vaikka meillä on tällaisia ​​yksinkertaisia ​​esimerkkejä 8 numeroa,

600
00:35:19,830 --> 00:35:24,000
voit päätellä helposti 8 verkkosivuja, 8000000000 web-sivuja,

601
00:35:24,000 --> 00:35:26,680
tai 800000000 ystäviä Facebookissa.

602
00:35:26,680 --> 00:35:30,090
Joten nämä algoritmit voidaan varmasti skaalata tuollaiset arvot,

603
00:35:30,090 --> 00:35:32,300
ja ideat ovat lopulta sama.

604
00:35:32,300 --> 00:35:36,140
Joten kupla sort oli ensimmäinen, jossa me tavallaan kuplina ylös suurin henkilö

605
00:35:36,140 --> 00:35:39,110
aina oikealla vaihtamalla ihmisiä pareittain.

606
00:35:39,110 --> 00:35:42,040
Sitten meillä oli mitä me kutsumme valinta lajitella jossa olen hieman tarkoituksellisesti

607
00:35:42,040 --> 00:35:46,480
katseli luettelon läpi, valitaan pienin numero uudestaan ​​ja uudestaan ​​ja uudestaan,

608
00:35:46,480 --> 00:35:49,530
looginen seuraus on, että lista on lopulta lajitellaan.

609
00:35:49,530 --> 00:35:53,780
Sitten kolmas, lisäsin ihmiset oikeisiin paikkaan,

610
00:35:53,780 --> 00:35:57,720
ja teimme hyvin keinotekoinen esimerkki siitä, että luettelo on jo lajiteltu,

611
00:35:57,720 --> 00:36:01,100
mutta se oli lähettää viesti, että lisäys lajitella tapauksessa,

612
00:36:01,100 --> 00:36:02,670
saat onnekas.

613
00:36:02,670 --> 00:36:07,930
Jos numeroita on jo lajiteltu, se vain vie sinut n askelta vahvistaa niin paljon,

614
00:36:07,930 --> 00:36:10,870
katsoo valinta lajitella olet hieman putkinäkö

615
00:36:10,870 --> 00:36:14,360
ja et koskaan ymmärrä, että luettelo on jo järjestetty.

616
00:36:14,360 --> 00:36:16,830
Joten katsotaanpas kupla lajitella toiminnassa täällä.

617
00:36:16,830 --> 00:36:19,590
Seuraavassa esimerkissä aiomme nähdä pystypalkki

618
00:36:19,590 --> 00:36:23,030
joiden korkeudet ovat numeroita, jotta voimme tavallaan visualisoida lajittelu tapahtuu.

619
00:36:23,030 --> 00:36:26,630
Pienempi palkki, pienempi numero, sitä suurempi palkki, isompi numero.

620
00:36:26,630 --> 00:36:28,860
>> Ja me pelata sitä tällä oletuksena nopeudella.

621
00:36:28,860 --> 00:36:33,460
Se tulee liikkua hieman nopeasti nyt, mutta punainen on mitä näyttää 2 baaria

622
00:36:33,460 --> 00:36:35,480
verrataan vierekkäin.

623
00:36:35,480 --> 00:36:39,520
Ja jos katsot tarkkaan, mitä tapahtuu on että jos baarit ovat epäkunnossa,

624
00:36:39,520 --> 00:36:42,300
pienempi kukaan siirretään vasemmalle, sitä suurempi yhdellä oikealle,

625
00:36:42,300 --> 00:36:44,360
ja sitten pidät etenee.

626
00:36:44,360 --> 00:36:48,520
Joten jos teemme tämän uudestaan ​​ja uudestaan, huomaan, että pienin baarit

627
00:36:48,520 --> 00:36:51,090
tulevat pitämään inching tiensä vasempaan

628
00:36:51,090 --> 00:36:54,130
ja suurimmat baarit ovat menossa pitämään inching tiensä oikealle.

629
00:36:54,130 --> 00:36:58,490
Ja todellakin, olemme alkaneet nähdä kuvion koko matkan oikealla puolella

630
00:36:58,490 --> 00:37:04,790
kuten näimme 8 ja sitten 7 lopulta kuplii asti perällä meidän ihmisten listan.

631
00:37:04,790 --> 00:37:08,750
Joten tämä tulee hyvin nopeasti saada vähän tylsiä, joten haluan lopettaa tämän hetkeksi.

632
00:37:08,750 --> 00:37:10,980
Saanen muuttaa nopeutta olla paljon nopeampi.

633
00:37:10,980 --> 00:37:15,380
En muuttamalla algoritmia, olen juuri tekemässä animaatiota tapahtua nopeammin.

634
00:37:15,380 --> 00:37:18,410
Silti kupla lajitella, sama algoritmi,

635
00:37:18,410 --> 00:37:21,910
mutta nyt voit nähdä paljon nopeampi kuin sanallinen esittely

636
00:37:21,910 --> 00:37:25,900
että suurin elementit ovat todellakin kuplivat ylös.

637
00:37:25,900 --> 00:37:29,860
>> Sivuhuomautuksena, nämä pikku neliöt alareunassa vasemmalla ja alhaalla oikealla

638
00:37:29,860 --> 00:37:33,520
ovat vain pieniä muistutuksia siitä, kuinka monta vertailua teet.

639
00:37:33,520 --> 00:37:37,620
Mutta nyt voimme keskittyä pyramidin, joka on muotoutumassa, ja siellä se menee.

640
00:37:37,620 --> 00:37:41,510
Pienin elementti on vasemmalla, suurin oikealla, ja kaikki muu siltä väliltä.

641
00:37:41,510 --> 00:37:44,470
Nyt sen sijaan katsomaan valinta lajitella.

642
00:37:44,470 --> 00:37:47,260
Aion mennä eteenpäin ja iski Seis. Aiomme saada uusi satunnainen joukko baareja.

643
00:37:47,260 --> 00:37:50,930
Valinta lajitella, Recall, kulkee listan uudestaan ​​ja uudestaan ​​ja uudestaan,

644
00:37:50,930 --> 00:37:54,900
nyppiminen ulos pienin elementti. Joten tässä on valinta tavallaan.

645
00:37:54,900 --> 00:37:58,390
Näyttää siltä, ​​että on vähemmän töitä tapahtuu nyt, koska emme verrataan pareittain

646
00:37:58,390 --> 00:38:02,590
mutta me vain eräänlainen cherry picking pienin elementtejä oikealta vasemmalle.

647
00:38:02,590 --> 00:38:06,890
Se kesti hyvin vähän aikaa, joten siellä kahtiajako jo.

648
00:38:06,890 --> 00:38:11,820
Vain koska algoritmi on sanottu n potenssiin aikaa, kuten kupla lajitella

649
00:38:11,820 --> 00:38:16,100
ja kuten valinta lajitella, nämä ovat oikeastaan ​​pahin käyntiaikoja.

650
00:38:16,100 --> 00:38:21,790
Esimerkiksi tapauksessa, sanokaamme, valinta lajitella,

651
00:38:21,790 --> 00:38:27,240
Olen itse olen valinnut pienin ihminen ja laittaa hänet tänne,

652
00:38:27,240 --> 00:38:29,620
Sitten teen sen taas, niin teen sen taas,

653
00:38:29,620 --> 00:38:32,070
mutta oli hieman optimointi voisin tehdä.

654
00:38:32,070 --> 00:38:35,040
>> Heti kun muutin numero 1 täällä - Sammy tässä tapauksessa -

655
00:38:35,040 --> 00:38:38,630
mitäs minun pitää tehdä hänen kanssaan sen jälkeen? >> [Opiskelija] Jätä hänet.

656
00:38:38,630 --> 00:38:40,140
Jätä hänet, eikö? Mitään.

657
00:38:40,140 --> 00:38:44,310
En tarvitse koskaan puhua Sammy uudelleen, koska jos olisin valinnut pienimmän alkion

658
00:38:44,310 --> 00:38:48,580
ja laittaa hänet tänne, miksi tuhlata aikaa menossa loppuun minun koko lista?

659
00:38:48,580 --> 00:38:54,590
Seuraavalla iteraation haluan tosiasiallisesti liikkua vain numero 2, vain numero 3.

660
00:38:54,590 --> 00:38:57,640
Joten todellisuudessa, en ollut tekemässä n asioita n kertaa.

661
00:38:57,640 --> 00:39:05,380
Tein n asioita, niin n - 1 asioita, niin n - 2 asioita, niin n - 3 asioita,

662
00:39:05,380 --> 00:39:07,080
sitten n - 4, piste, piste, dot.

663
00:39:07,080 --> 00:39:09,470
Meillä on hieman geometrisen sarjan, mikä juuri tarkoittaa

664
00:39:09,470 --> 00:39:11,450
lisäät ylös asteittain pienempiä numeroita.

665
00:39:11,450 --> 00:39:17,940
Ei n + n + n + n, mutta n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Ja mitä se yleensä toimii osoittautua -

667
00:39:21,380 --> 00:39:24,280
Aion sotkea minun aluksella täällä vain hetken -

668
00:39:24,280 --> 00:39:28,990
että menee treenata olla jotain n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
jos me vain eräänlainen katsaus takana matematiikka kirja, jossa sinulla on kaikki huijata levyt

670
00:39:31,930 --> 00:39:33,410
varten kaavojen.

671
00:39:33,410 --> 00:39:37,760
Jos olet vain lisäämällä jotain n + n - 1 + n - 2, se toimii olla jotain tällaista.

672
00:39:37,760 --> 00:39:42,320
Ja jos me vain eräänlainen moninkertaistaa tämän, joka on n: n potenssiin miinus N / 2.

673
00:39:42,320 --> 00:39:46,400
Sanoin n potenssiin, vaikka, ja se on koska olin tavallaan ottaa henkinen oikotie

674
00:39:46,400 --> 00:39:51,950
koska todellisuudessa n potenssiin miinus N jaettuna 2 on todellakin totta askelmäärä

675
00:39:51,950 --> 00:39:55,510
että algoritmi valinta Lajittele veisi jos todella lasketaan ylös

676
00:39:55,510 --> 00:39:58,800
kaikki nämä vertailut ja kaikki pikku kiireinen työ olimme tekemässä.

677
00:39:58,800 --> 00:40:03,210
Mutta rehellisesti, kun n saa olla kuin miljoona tai miljardi, joka hitossa välittää

678
00:40:03,210 --> 00:40:07,160
Jos teet miljardin neliön miinus miljardi jaettuna 2?

679
00:40:07,160 --> 00:40:09,320
Miljardia squared on valtava määrä.

680
00:40:09,320 --> 00:40:13,580
Voit ottaa toisen miljardin pois sitä - n. Se ei ole niin iso juttu.

681
00:40:13,580 --> 00:40:18,770
Joten isompi numerot saavat, vähemmän tärkeitä nämä alemmat järjestettyä ehdot ovat.

682
00:40:18,770 --> 00:40:24,230
Ketä kiinnostaa, jos jaat 2 jos puhut quadrillions numerot vaiheita?

683
00:40:24,230 --> 00:40:29,710
>> Joten yleensä tietojenkäsittelyasiantuntijat taipumus heittää pois kaiken, mutta suurimmat aikavälillä,

684
00:40:29,710 --> 00:40:33,140
ja me vain eräänlainen yksinkertaistaa maailmaa ja sanoa, että algoritmi

685
00:40:33,140 --> 00:40:38,130
kesti noin n potenssiin vaiheita. Tuo käyntiaika algoritmin.

686
00:40:38,130 --> 00:40:40,760
Joten me palaamme tähän vain hetki joitakin konkreettisia esimerkkejä,

687
00:40:40,760 --> 00:40:45,940
mutta nyt se on eräänlainen intuitiivinen motivaatio juuri yksinkertaistamalla maailman

688
00:40:45,940 --> 00:40:51,170
ja puhumme tärkein eikä niinkään joutumassa kaikki nämä fancy kaavat.

689
00:40:51,170 --> 00:40:53,540
Joten se oli valinta lajitella, ja saimme hieman onnekas siellä.

690
00:40:53,540 --> 00:40:57,360
Katsotaanpa paikoilleen lajitella. Anna minun mennä eteenpäin ja aloittaa tämän yhtä hyvin.

691
00:40:57,360 --> 00:41:00,330
Nyt huomaa malli, joka tapahtuu on hieman erilainen,

692
00:41:00,330 --> 00:41:03,410
ja aloitimme satunnaislukuja,

693
00:41:03,410 --> 00:41:06,890
mutta jos me todella laskea portaiden lukumäärän pahimmassa tapauksessa

694
00:41:06,890 --> 00:41:11,070
Jos lista alkoi täysin oikeassa järjestyksessä,

695
00:41:11,070 --> 00:41:13,380
me kestäisi vain n toimet toteuttaa mahdollisimman paljon.

696
00:41:13,380 --> 00:41:18,240
>> Mutta jos luettelossa olivat todella taaksepäin - esimerkiksi tässä tapauksessa täällä -

697
00:41:18,240 --> 00:41:23,860
Sitten huomaa meillä on todellakin tehtävä paljon enemmän työtä tässä asiassa.

698
00:41:23,860 --> 00:41:27,080
Ja se olisi sellainen tunne sinua, kuten tässä on kaikenlaista valmistusta kovemmin

699
00:41:27,080 --> 00:41:30,900
saada ne pienet elementit vasemmalle, ja se johtuu siitä saimme epäonninen.

700
00:41:30,900 --> 00:41:34,210
Luettelo lajitellaan vahingossa taaksepäin.

701
00:41:34,210 --> 00:41:38,110
Sen sijaan insertiovektorilla sort jos me matkia mitä teimme meidän ihmisten täällä

702
00:41:38,110 --> 00:41:42,670
aloittamalla kaikkien kanssa lajitellaan ja käynnistä, se on aika hyvä algoritmi, eikö?

703
00:41:42,670 --> 00:41:45,010
Se on jo itse asiassa, lajitellaan.

704
00:41:45,010 --> 00:41:48,670
Joten yritä tiivistää kuinka paljon aikaa näitä asioita otetaan yhteyttä

705
00:41:48,670 --> 00:41:52,360
ottamalla käyttöön vain vähän ammattikieltä tai merkintää, joka on todella paljon yksinkertaisempi

706
00:41:52,360 --> 00:41:54,320
kuin fanciness sellaista ehdottaa.

707
00:41:54,320 --> 00:41:59,030
Tämä juttu täällä, tämä iso O ruudulla, mitä tietojenkäsittelytieteessä yleensä käyttää

708
00:41:59,030 --> 00:42:03,640
kuvaamaan pahimmassa tapauksessa käyntiaika algoritmi.

709
00:42:03,640 --> 00:42:07,360
>> Jälleen jota pahimmassa tapauksessa se on täysin kontekstisidonnaisia.

710
00:42:07,360 --> 00:42:10,890
Mitä me tarkoitamme pahimmassa tapauksessa kokonaan vaihtelee ongelmasta puhumme.

711
00:42:10,890 --> 00:42:14,550
Mutta kyse lajittelun, mikä on pahin mahdollinen skenaario?

712
00:42:14,550 --> 00:42:17,860
Kaikki on taaksepäin, koska se vain tuntuu, että merkitsee paljon työtä meille.

713
00:42:17,860 --> 00:42:21,330
Olen jotted alas muutamia algoritmeja, jotka olemme nähneet tähän mennessä:

714
00:42:21,330 --> 00:42:24,930
lineaarinen haku, binäärihakupuu kuten kanssa puhelinluettelosta tai paperinpaloja,

715
00:42:24,930 --> 00:42:28,960
Sitten kupla lajitella, valinta lajitella ja lisäys lajitella kuten näimme meidän ihmisten,

716
00:42:28,960 --> 00:42:31,770
ja sitten 1 muu, joka on lopulta olemaan nimeltään yhdistää tavallaan.

717
00:42:31,770 --> 00:42:37,710
Joten lineaarinen haku pahimmassa tapauksessa, kuinka monta askelta kestää löytää numero 7

718
00:42:37,710 --> 00:42:40,690
jos on olemassa n ovia kuten Sean pinnoitettu? >> [Opiskelija] N.

719
00:42:40,690 --> 00:42:44,180
N. Niinpä aiomme kirjoittaa ison O n.

720
00:42:44,180 --> 00:42:47,010
Menen vain täyttää joitakin aihioita. Tämä on vain ruudukon aihioita.

721
00:42:47,010 --> 00:42:52,990
Mutta parhaassa tapauksessa lineaarista hakua, 7 olisi ollut aivan alussa luettelon

722
00:42:52,990 --> 00:42:55,520
ja Sean ehkä ovat alkaneet etsiä alussa luettelosta.

723
00:42:55,520 --> 00:42:58,940
Joten jos käytät lineaarista hakua ja vain tarkistaa vasemmalta oikealle tai ehkä oikealta vasemmalle -

724
00:42:58,940 --> 00:43:02,650
he vastaavat - parhaassa tapauksessa kuinka monta askelta voisi lineaarinen haku,

725
00:43:02,650 --> 00:43:05,550
kuten Sean algoritmi toteuttaa? Vain 1 askel.

726
00:43:05,550 --> 00:43:09,450
>> Joten aion sanoa, että se omega merkintää.

727
00:43:09,450 --> 00:43:11,570
Tämä on vain pääkaupunki omega.

728
00:43:11,570 --> 00:43:15,000
Omega on vain seksikäs tapa sanoa Parhaassa tapauksessa käyntiajan.

729
00:43:15,000 --> 00:43:18,900
Joten parhaassa tapauksessa käyntiaika on yhdessä vaiheessa tai jatkuvasti useita vaiheita -

730
00:43:18,900 --> 00:43:24,270
1 tässä tapauksessa - mutta pahimmassa tapauksessa iso O, se on todella n askelta.

731
00:43:24,270 --> 00:43:28,110
Ja tämä tässä, theta, emme oikeastaan ​​ole menossa katsomaan juuri nyt.

732
00:43:28,110 --> 00:43:30,090
Se ei ole merkitystä tässä esimerkissä.

733
00:43:30,090 --> 00:43:31,990
Mutta nyt Kokeillaan binäärihakupuu.

734
00:43:31,990 --> 00:43:35,990
Pahimmassa tapauksessa binäärihakupuu, kuinka monta askelta se aikoo ryhtyä löytääkseen numero 7

735
00:43:35,990 --> 00:43:38,340
tai mitä etsimme? >> [Opiskelija] log n.

736
00:43:38,340 --> 00:43:40,980
Vielä menossa ottamaan log n, koska aivan kuten Alex sai epäonninen

737
00:43:40,980 --> 00:43:44,030
kun me todellakin käyneet läpi ongelmaa suunnitelmallisesti

738
00:43:44,030 --> 00:43:48,220
ja hän ei löydä numero 7, kunnes aivan viime oven hän katseli,

739
00:43:48,220 --> 00:43:51,720
vaikka oikeudenmukaisuus, hän sai heittää pois tiettyjä ovia matkan varrella,

740
00:43:51,720 --> 00:43:56,920
binäärihakupuu pahimmassa tapauksessa on ajoaika log n.

741
00:43:56,920 --> 00:43:59,230
Ja vielä, että puhuu tästä jakamalla ja valloitusta.

742
00:43:59,230 --> 00:44:01,140
Mutta entä parhaassa tapauksessa?

743
00:44:01,140 --> 00:44:04,790
Ja Alex todella kokenut, että parhaassa tapauksessa oikeassa, kun hän tuli lavalle.

744
00:44:04,790 --> 00:44:07,290
Kuinka monta askelta ei joka toteuttaa binäärihakupuu? >> [Opiskelija] 1.

745
00:44:07,290 --> 00:44:09,380
1, vain koska hän sai onnekas.

746
00:44:09,380 --> 00:44:12,520
Mutta se on hienoa, koska omega viittaa parhaassa tapauksessa skenaarioita,

747
00:44:12,520 --> 00:44:15,770
Parhaassa tapauksessa tuloa, vaikka se on vain satunnainen tyhmä onnea.

748
00:44:15,770 --> 00:44:18,900
>> Nyt tämäkin aiomme juuri sellainen Jätä tyhjäksi nyt.

749
00:44:18,900 --> 00:44:21,010
Entä nyt kupla lajitella?

750
00:44:21,010 --> 00:44:24,290
Pahimmassa tapauksessa kupla lajitella, kaikki on käänteisessä järjestyksessä,

751
00:44:24,290 --> 00:44:26,380
joten meidän täytyy tehdä paljon kuplivaa.

752
00:44:26,380 --> 00:44:30,190
Mutta kuinka monta askelta on joka vie pahimmassa tapauksessa? >> [Opiskelija] N potenssiin.

753
00:44:30,190 --> 00:44:32,550
Tämä oli n potenssiin, koska jos ajattelee sitä,

754
00:44:32,550 --> 00:44:36,410
jos lista on täysin taaksepäin - 8 on täällä, 1 on täällä -

755
00:44:36,410 --> 00:44:40,530
koska asia alkaa kupla, numero 8 tulee näin liikkua, näin,

756
00:44:40,530 --> 00:44:44,540
Näin tämä tapa, mutta jossa on numero 7 pahimmassa tapauksessa?

757
00:44:44,540 --> 00:44:47,720
Tässä hän on yhä tuolla. Joten meidän täytyy tehdä se uudestaan ​​ja uudestaan.

758
00:44:47,720 --> 00:44:53,190
Ja siitä saamme n askelta, niin n - 1 vaiheet, niin n - 2 askelta.

759
00:44:53,190 --> 00:44:55,960
Ja jos otat minun sanaani - että jos sellainen moninkertaistaa sen,

760
00:44:55,960 --> 00:45:00,110
Se on suunnilleen n: n neliön lopulta joidenkin muiden ehtojen että me vain sivuuttaa nyt -

761
00:45:00,110 --> 00:45:06,890
sitten pahimmassa tapauksessa kupla tavallaan on n potenssiin, antaa tai ottaa.

762
00:45:06,890 --> 00:45:09,490
Mutta entä parhaiten tapauksessa kupla lajitella?

763
00:45:09,490 --> 00:45:13,050
Mikä on paras skenaario? Kaikki numerot ovat järjestetty jo.

764
00:45:13,050 --> 00:45:15,920
Ja mikä oli heuristinen käytin, temppu käytin,

765
00:45:15,920 --> 00:45:20,110
ymmärtää, että olisin tehnyt mitään työtä, ja voisi näin ollen lopettaa aikaisin?

766
00:45:20,110 --> 00:45:23,590
[Opiskelija] Tarkista se kerran. >> Tarkista kerran. Mutta mitä teen matkan varrella?

767
00:45:23,590 --> 00:45:26,130
Olin pitää kirjaa kuinka monta swap tein.

768
00:45:26,130 --> 00:45:30,650
Ja tajusin, jos en ole laskenut mitään swap minun sormet, niin olen tehnyt mitään työtä.

769
00:45:30,650 --> 00:45:34,300
En todellakaan pitäisi yrittää tehdä mitään työtä jälleen, joten voin vain lopettaa.

770
00:45:34,300 --> 00:45:37,830
>> Joten paras jos kupla lajitella, kun luettelo on jo järjestetty,

771
00:45:37,830 --> 00:45:41,530
mitä sanoisit Omega notaatio on, parhaimmassa tapauksessa käyntiaika?

772
00:45:41,530 --> 00:45:48,040
Se on vain N. Meidän täytyy tehdä työtä, mutta meillä on vain tehtävä 1 kävelymatkan verran työtä.

773
00:45:48,040 --> 00:45:50,490
Ja tässäkin aion jättää tämän osan tyhjäksi.

774
00:45:50,490 --> 00:45:52,430
Ja nyt valinta lajitella.

775
00:45:52,430 --> 00:45:56,010
Valinta sort oli minulle nyppiminen pienin ihminen uudestaan ​​ja uudestaan.

776
00:45:56,010 --> 00:45:58,380
Ja mitä me sanomme käyntiaika se oli?

777
00:45:58,380 --> 00:46:00,590
Se oli n neliö pahimmassa tapauksessa.

778
00:46:00,590 --> 00:46:05,220
Ja valitettavasti, parhaassa tapauksessa se on myös N potenssiin

779
00:46:05,220 --> 00:46:08,840
koska minulla ei ole sellaista kaikkitietäviä näkymä koko maailmassa;

780
00:46:08,840 --> 00:46:13,140
Tiedän vain, kun koko iteraation että olen todellakin löytänyt pienin ihminen.

781
00:46:13,140 --> 00:46:15,860
Joten valinta tavallaan eräänlainen imee mielessä,

782
00:46:15,860 --> 00:46:17,920
mutta ylösalaisin on se eräänlainen intuitiivinen.

783
00:46:17,920 --> 00:46:21,470
Se on melko helppo koodata ylös, koska kaikki mitä tarvitsee tehdä on kirjoittaa pari sisäkkäisiä silmukoita,

784
00:46:21,470 --> 00:46:24,620
tyypillisesti, että menee läpi etsimässä pienimmän alkion

785
00:46:24,620 --> 00:46:27,840
ja sitten laittaa pienin elementti, johon se kuuluu lopussa luettelosta.

786
00:46:27,840 --> 00:46:29,900
Joten tässä myös siellä tulee olemaan kompromissi.

787
00:46:29,900 --> 00:46:34,440
Aikaa se vie sinut ajattelemaan ja todella kehittää jotain kirjoittaa koodia

788
00:46:34,440 --> 00:46:39,460
voisi hyvin viedä enemmän aikaa, jos haluat parempaa algoritmia ja nopeamman suorituskyvyn.

789
00:46:39,460 --> 00:46:41,780
>> Mutta jos todella juuri sellainen koodiin jotain nopeaa ja likainen

790
00:46:41,780 --> 00:46:45,000
ja juuri sellainen ottaa typerin mahdollinen idea voit ajatella,

791
00:46:45,000 --> 00:46:47,580
jotka voivat viedä sinut muutaman minuutin koodia, mutta suuria tietomääriä

792
00:46:47,580 --> 00:46:49,580
algoritmisi voi kestää tunnin ajaa.

793
00:46:49,580 --> 00:46:51,690
Ja vaikka minä tutkijakoulussa joskus tehdä näistä kompromisseja.

794
00:46:51,690 --> 00:46:55,660
Olisi 3am, yritin analysoida erittäin suuri tietokokonaisuutta

795
00:46:55,660 --> 00:46:59,650
turvallisuuteen liittyvät tutkimus tein, ja se oli joko viettää 5 minuuttia

796
00:46:59,650 --> 00:47:03,210
säätämistä minun ohjelma analysoida tietoja ja mennä nukkumaan

797
00:47:03,210 --> 00:47:08,420
tai viettää 8 tuntia saada se juuri oikea, joten se toimii heti ja mennä nukkumaan.

798
00:47:08,420 --> 00:47:10,530
Ja niin siellä se tavallaan tietoisen päätöksen.

799
00:47:10,530 --> 00:47:12,740
Vähemmän kehityksen aikaa, enemmän unta.

800
00:47:12,740 --> 00:47:14,780
Jälkeenpäin en luultavasti pitäisi kannustaa, että

801
00:47:14,780 --> 00:47:19,120
kun tavoitteena tässä on optimoida koodin laatu,

802
00:47:19,120 --> 00:47:21,280
mutta sekin todellisessa maailmassa on hyvin kohtuullinen kompromissi.

803
00:47:21,280 --> 00:47:25,130
Vähemmän aikaa, vähemmän suorituskykyä tai päinvastoin.

804
00:47:25,130 --> 00:47:28,110
Joten tässä meillä vihdoinkin mahdollisuus puhua theta.

805
00:47:28,110 --> 00:47:32,830
Theta merkintätapa on jotain tietojenkäsittelyasiantuntijat voi tuoda esille keskustelun

806
00:47:32,830 --> 00:47:36,160
kun iso O-ja omega sattuvat olemaan sama.

807
00:47:36,160 --> 00:47:40,160
Sanot theta todella lähettää viestin, että tämä on tällainen tiukka sidottu.

808
00:47:40,160 --> 00:47:43,340
Ei ole väliä onko skenaario on hyvä tai huono, se on n: n potenssiin.

809
00:47:43,340 --> 00:47:46,510
Joten se ei vain ole merkitystä näitä tarinoita täällä.

810
00:47:46,510 --> 00:47:48,560
Insertion sort on viimeinen me katsoimme,

811
00:47:48,560 --> 00:47:50,830
jossa olin juuri laittamalla jokaiselle oikeaan paikkaan.

812
00:47:50,830 --> 00:47:54,930
Parhaassa tapauksessa mikä oli käyntiaika paikoilleen tavallaan kuin näimme sen täällä?

813
00:47:54,930 --> 00:47:57,250
[Opiskelija] Parhaassa tapauksessa? >> Parhaassa tapauksessa.

814
00:47:57,250 --> 00:48:00,100
>> Se oli N, koska parhaassa tapauksessa kaikki lajitellaan,

815
00:48:00,100 --> 00:48:02,580
ja Sammy ja kukaan muu todella oli liikkua ollenkaan.

816
00:48:02,580 --> 00:48:04,610
He olivat jo niiden oikeaan paikkaan.

817
00:48:04,610 --> 00:48:08,570
Joten insertion sort parhaassa tapauksessa, tässä tapauksessa n..

818
00:48:08,570 --> 00:48:12,770
Mutta pahimmassa tapauksessa se on eräänlainen n: n neliö. Miksi?

819
00:48:12,770 --> 00:48:16,230
Jos lista ihmisten on käänteisessä järjestyksessä,

820
00:48:16,230 --> 00:48:21,260
Minä ensin aloittaa numerolla 8 ja asetan hänet oikeaan asentoon, mikä on täällä.

821
00:48:21,260 --> 00:48:25,270
Olen sellainen siirtyä puolelle. Nämä kaverit ovat lajittelemattomina, hän on lajiteltu.

822
00:48:25,270 --> 00:48:28,970
Mutta nyt satun löytää kuka seuraavaksi? >> [Opiskelija] 7.

823
00:48:28,970 --> 00:48:31,250
7 pahimmassa tapauksessa, koska se on päinvastaisessa järjestyksessä.

824
00:48:31,250 --> 00:48:34,920
>> Joten tässä on 7. Mistä 7 kuuluu? Ehdottomasti takanani.

825
00:48:34,920 --> 00:48:39,460
Mutta nyt 7 todella kuuluu ei heti takanani mutta takana numero 8,

826
00:48:39,460 --> 00:48:41,880
joten minun täytyy sanoa, "Anteeksi, numero 8, voitteko siirtää tällä tavalla

827
00:48:41,880 --> 00:48:44,640
"Tehdä tilaa 7?" Nyt olen kohtaavat 6.

828
00:48:44,640 --> 00:48:48,530
"Anteeksi, numero 8 ja numero 7, voit siirtyä tehdä tilaa 6?"

829
00:48:48,530 --> 00:48:52,360
Eli toisin sanoen, lisäys lajitella, vaikka en tee paljon liikettä,

830
00:48:52,360 --> 00:48:56,330
ihmiset takanani tekevät paljon työtä, ja se on pakko maksaa joku kerta.

831
00:48:56,330 --> 00:48:58,000
Se tulee maksamaan tietokoneen aikaa.

832
00:48:58,000 --> 00:49:01,450
Joten jos insertion sort vielä kärsiä.

833
00:49:01,450 --> 00:49:06,260
Jos aloitat laskemalla kokonaismäärä vaiheita, päädymme lyömällä karkeasti n syrjätty

834
00:49:06,260 --> 00:49:11,160
koska nämä kaverit täytyy tehdä tilaa ihmisen lisätään takaisin tähän luetteloon.

835
00:49:11,160 --> 00:49:15,960
Ja niin tässä tapauksessa theta ei vain soveltaa erityistä tarinaa käsillä.

836
00:49:15,960 --> 00:49:21,100
Siinä kaikki kiva ja hyvä. Meillä on näitä 3 eri tapoja puhua käyntiaika.

837
00:49:21,100 --> 00:49:26,370
Mutta mitä tämä oikeastaan ​​tarkoittaa reaalisesti jos todella yrittää koodata jopa algoritmi?

838
00:49:26,370 --> 00:49:31,620
>> Saanen ehdottaa, että siellä on vieläkin parempi algoritmi siellä

839
00:49:31,620 --> 00:49:33,740
että itse on joitakin kompromisseja.

840
00:49:33,740 --> 00:49:36,890
Aiomme kutsua yhdistää lajitella, ja se on tavallaan tämän maagisen algoritmin

841
00:49:36,890 --> 00:49:42,840
että vain toimii nopeammin jotenkin, ja se on niin helppo ilmaista, ainakin pseudokoodilla.

842
00:49:42,840 --> 00:49:46,900
Täytäntöönpano algoritmin merge sort tulee olemaan seuraava.

843
00:49:46,900 --> 00:49:50,860
Kun olet antanut n elementit - n numerot, N ihmisiä riippumatta - ensimmäinen siellä järki tarkistaa.

844
00:49:50,860 --> 00:49:56,340
Jos n on pienempi kuin 2, yhdistää tavallaan vain pysähtyy. Se palaa, niin sanoakseni.

845
00:49:56,340 --> 00:50:00,830
Miksi lopetat jos n on pienempi kuin 2? >> [Äänetön opiskelijan vastausta]

846
00:50:00,830 --> 00:50:04,480
Oikea. Ja jälleen, n ei ole numeroa luettelossa, n on koko lista.

847
00:50:04,480 --> 00:50:07,660
Jos n on pienempi kuin 2, se tarkoittaa, että luettelo on joko 1,

848
00:50:07,660 --> 00:50:09,640
missä olet ilmeisesti lajitellaan jos se on 1 numero,

849
00:50:09,640 --> 00:50:11,710
tai 0, jolloin mikään ei lajitella,

850
00:50:11,710 --> 00:50:13,570
joten tarvitsemme tällaista perustapaus.

851
00:50:13,570 --> 00:50:20,350
Jos lista on niin lyhyt, että siellä on vain mitään tekemistä, kirjaimellisesti älä tee mitään. Return.

852
00:50:20,350 --> 00:50:25,090
Muuten lajitella vasen puoli elementit, sitten lajitella oikealla puolella elementtejä,

853
00:50:25,090 --> 00:50:27,410
sitten yhdistää 2 lajiteltu puolikkaat.

854
00:50:27,410 --> 00:50:32,130
>> Tällainen tuntuu hieman huijata, jossa pyydän teitä miten lajitella elementtejä

855
00:50:32,130 --> 00:50:34,900
ja sanot, "Lajittele vasen puoli, lajitella oikea puoli."

856
00:50:34,900 --> 00:50:37,240
Olen kuin, "Okei. Miten lajitella vasen puoli?"

857
00:50:37,240 --> 00:50:40,670
"Lajittele vasen puoli vasen puoli, lajitella oikea puoli vasemman puolen, ja sitten tehty."

858
00:50:40,670 --> 00:50:44,060
Olet sellainen syklisesti määritellä mitä tarkoittaa lajitella,

859
00:50:44,060 --> 00:50:46,790
mutta näyttää siltä, ​​että on todella loistava tässä tapauksessa.

860
00:50:46,790 --> 00:50:50,230
Se ei ole hyvä tämä noidankehä, joka ei lopu koskaan

861
00:50:50,230 --> 00:50:52,550
koska se ei pääty siihen, kun? >> [Opiskelija] Kun tulet 1 asia.

862
00:50:52,550 --> 00:50:54,220
Kun tulet 1 asia.

863
00:50:54,220 --> 00:50:57,850
Joten vaikka saatat aloittaa 8 henkilöä ja sanon, "Lajittele vasen puoli näistä ihmisistä,

864
00:50:57,850 --> 00:51:00,480
nämä 4 ihmistä, "sanon," Miten lajitella vasen puoli? "

865
00:51:00,480 --> 00:51:03,450
"No, lajitella 2 täällä." Ja sitten olet kuin "Okei, hienoa."

866
00:51:03,450 --> 00:51:05,520
"Miten lajitella vasemmalla puolella nuo ihmiset?"

867
00:51:05,520 --> 00:51:09,040
"Juuri lajitella tätä 1 henkilö täällä." Mikä loistava ilmestys nyt?

868
00:51:09,040 --> 00:51:13,050
Minun täytyy lajitella 1 henkilö. Valmis. Minulla ei ole tehdä mitään työtä.

869
00:51:13,050 --> 00:51:16,580
Mutta nyt minun täytyy selvittää tämä henkilö, mutta he yksi henkilö, ei ole mitään tekemistä.

870
00:51:16,580 --> 00:51:21,490
>> Joten taika ilmeisesti on tässä kolmannessa vaiheessa: yhdistää lajiteltu puolikkaat.

871
00:51:21,490 --> 00:51:25,770
Joten yhdistää tavallaan vie tämä loistava oivallus, että jos rikot iso ongelma alas

872
00:51:25,770 --> 00:51:28,650
osaksi 2 pienempää, identtisesti kokoinen ongelmia

873
00:51:28,650 --> 00:51:32,710
ja sitten vain eräänlainen liima pienempiä ratkaisuja yhdessä lopussa,

874
00:51:32,710 --> 00:51:34,720
Ehdotan, että voimme tehdä paljon, paljon parempi [napauttamalla ääni]

875
00:51:34,720 --> 00:51:38,050
kuin mikään valinta lajitella tai insertion sort.

876
00:51:38,050 --> 00:51:40,690
Olen itse ollut piittaamatta, että puoli tuntia, mutta en todellakaan tiedä mitä tapahtuu

877
00:51:40,690 --> 00:51:45,040
ulkopuolella tänään. [Surinaa] [naurua]

878
00:51:45,040 --> 00:51:49,660
Joten jos voimme nähdä tätä vähän apua ystävämme Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
On 2 suuria askeleita prosessissa merge sort.

880
00:51:52,810 --> 00:51:56,400
Ensinnäkin, jatkuvasti jakaa luettelon kupit kahtia

881
00:51:56,400 --> 00:51:59,610
kunnes meillä on nippu luetteloita vain 1 kuppi niihin.

882
00:51:59,610 --> 00:52:02,150
Älä huolestu, jos luettelo sisältää parittoman määrän

883
00:52:02,150 --> 00:52:04,830
ja et voi tehdä täysin puhdas leikkaus välillä.

884
00:52:04,830 --> 00:52:08,740
Aivan mielivaltaisesti valita mikä lista sisältää ylimääräisiä kupin sisään

885
00:52:08,740 --> 00:52:11,320
Joten jakaa näitä listoja.

886
00:52:12,420 --> 00:52:14,570
Nyt meillä on 2 luetteloita.

887
00:52:18,930 --> 00:52:20,930
Nyt meillä on 4 luetteloita.

888
00:52:25,730 --> 00:52:28,740
Nyt meillä on 8 luettelot yhden kupin kussakin luettelossa.

889
00:52:28,740 --> 00:52:31,520
Niin, että se vaihe 1.

890
00:52:31,520 --> 00:52:37,280
Vaiheessa 2 me toistuvasti yhdistää paria luetteloiden avulla yhdistämisen algoritmia opimme ennen.

891
00:52:37,280 --> 00:52:44,320
Yhdistyminen 108 ja 15 päädymme luettelon 15, 108.

892
00:52:45,240 --> 00:52:51,330
Yhdistyminen 50 ja 4 päädymme 4, 50.

893
00:52:51,330 --> 00:52:56,950
Yhdistyminen 8 ja 42 päädymme 8, 42.

894
00:52:57,790 --> 00:53:04,360
Ja yhdistämällä 23 ja 16 päädymme 16, 23.

895
00:53:04,360 --> 00:53:08,030
Nyt kaikki luettelot ovat kooltaan 2.

896
00:53:08,030 --> 00:53:10,980
Huomaa, että kukin 4 luetteloiden on lajiteltu,

897
00:53:10,980 --> 00:53:14,230
jotta voimme aloittaa yhdistämällä paria luetteloiden uudelleen.

898
00:53:14,230 --> 00:53:22,150
Yhdistämällä 15 ja 108 sekä 4 ja 50 me toteuttaa ensin 4, sitten 15,

899
00:53:22,150 --> 00:53:26,250
sitten 50, sitten 108.

900
00:53:26,250 --> 00:53:33,020
Yhdistyminen 8, 42 ja 16, 23 ensin ottaa 8, sitten 16,

901
00:53:33,020 --> 00:53:37,170
sitten 23, sitten 42.

902
00:53:37,170 --> 00:53:42,490
Nyt meillä on siis vain 2 luettelot koko 4, joista kukin on järjestetty.

903
00:53:42,490 --> 00:53:45,940
Joten nyt me yhdistää nämä 2 luetellaan.

904
00:53:45,940 --> 00:53:54,230
Ensin otamme 4, niin otamme 8, niin otamme 15

905
00:53:54,230 --> 00:54:05,280
ja 16 ja 23 sekä 42 ja 50 ja 108.

906
00:54:05,280 --> 00:54:09,020
Ja olemme tehneet. Meillä on nyt lajiteltu luettelo.

907
00:54:09,020 --> 00:54:13,740
>> Rob oli eräänlainen hyödyntää jotain, että emme ole vielä tehneet.

908
00:54:13,740 --> 00:54:16,540
Ehdotettiin, mutta emme todella tehdä sen.

909
00:54:16,540 --> 00:54:19,230
Hän tekee jotain fyysisesti kupit joka viittaa

910
00:54:19,230 --> 00:54:23,680
hän vietti jonkin resurssin lisäksi aikaa. >> [Opiskelija] Space. >> Se oli tilaa.

911
00:54:23,680 --> 00:54:27,360
Se, että hänellä oli tällainen kahden tason taulukko, jossa hän oli tilaa täällä

912
00:54:27,360 --> 00:54:31,960
ja tilaa täällä todella ymmärtää, että hän käyttää kaksi kertaa niin paljon tilaa

913
00:54:31,960 --> 00:54:36,390
koska kaikki meidän algoritmeja toistaiseksi - lisäys lajitella, kupla lajitella tai valinta lajitella -

914
00:54:36,390 --> 00:54:40,780
mutta hän oli hyödyntäen tätä ylimääräistä tilaa eräänlainen siirrellä edestakaisin

915
00:54:40,780 --> 00:54:42,600
pitäen asiat järjestyksessä.

916
00:54:42,600 --> 00:54:47,540
Ja vaikka se tuntuu saimme järjestetty luettelo, että tuntui kuin se kesti jonkin aikaa.

917
00:54:47,540 --> 00:54:51,060
Todellisuudessa Rob teki oli juuri tämä algoritmi.

918
00:54:51,060 --> 00:54:56,780
Aluksi hän otti ongelman koko n, jaettu sen vasen puoli ja oikea puoli.

919
00:54:56,780 --> 00:54:59,380
Silloin hän muutti kupit. Sitten hän toisti, että prosessi.

920
00:54:59,380 --> 00:55:03,390
Hän jakoi 4 tulee 2 sarjaa 2 tänne ja tänne.

921
00:55:03,390 --> 00:55:08,520
Sitten hän toisti prosessi ja jaetaan 2 tulee 2 sarjaa 1 kussakin eri kupit.

922
00:55:08,520 --> 00:55:11,000
Ja siitä loistava tilaisuuden tullen.

923
00:55:11,000 --> 00:55:15,840
Tuossa vaiheessa tarinan, Rob oli 8 luettelot koko 1,

924
00:55:15,840 --> 00:55:18,860
jotka kaikki järjestetty jo.

925
00:55:18,860 --> 00:55:20,630
>> Joten mitä hän jatkaa tehdä?

926
00:55:20,630 --> 00:55:25,260
Parittainen hän otti tämän järjestetty luettelo, ja tämä lajiteltu luettelo ja yhdistettiin ne.

927
00:55:25,260 --> 00:55:28,200
Sitten hän otti tämän yhden ja yhdistettiin ne, niin tämä yksi ja yhdistettiin ne,

928
00:55:28,200 --> 00:55:30,670
Sitten tämä yksi ja yhdistettiin ne.

929
00:55:30,670 --> 00:55:32,390
Ja mitä sitten hän teki seuraavaksi?

930
00:55:32,390 --> 00:55:36,580
Hän sitten uudelleen yhdistyivät isompi luettelot ja sitten uudelleen yhdistyivät isompi luettelot.

931
00:55:36,580 --> 00:55:41,170
Ja jos ajattelet tästä juuri intuitiivisesti nyt, mitä hän oikeasti tekee?

932
00:55:41,170 --> 00:55:45,450
Hän oli jakamalla ongelma puoli, on puoli, on puoli, että puoli

933
00:55:45,450 --> 00:55:47,600
saadakseen nämä tosi pieni luettelot.

934
00:55:47,600 --> 00:55:51,290
Sitten hän oli tavallaan yhdistyvät double, double, double, double.

935
00:55:51,290 --> 00:55:54,120
Niinpä hän teki kaksi kertaa niin paljon työtä kuin olemme nähneet tähän mennessä

936
00:55:54,120 --> 00:55:56,930
mitään mukana hajota ja hallitse, mutta no big deal.

937
00:55:56,930 --> 00:55:59,630
Kaksinkertainen työ ei ole niin iso juttu. Se on vain vakio.

938
00:55:59,630 --> 00:56:03,920
Ja aivan kuten meidän aritmeettinen lauseke ennen, olen juuri menossa yliviivata vakio tekijät

939
00:56:03,920 --> 00:56:10,170
kuten kertaa 2. Ketä kiinnostaa? Jos se on 2 miljardia kertaa 2, että on vielä paljon vaiheita.

940
00:56:10,170 --> 00:56:13,160
Joten tämä yhdistäminen vaihe näyttää olevan keskeinen oivallus.

941
00:56:13,160 --> 00:56:17,000
Kävellään kautta juuri numeerisesti ennen - Sepä ei saa jatkaa vielä.

942
00:56:17,000 --> 00:56:22,890
Kävellään kautta numeerisesti vain todella nähdä miten tämä soittaa ulos.

943
00:56:22,890 --> 00:56:25,940
Tämä on useimmiten vain pienen köyhän miehen animaatio.

944
00:56:25,940 --> 00:56:27,750
Mennään ehdottaa tätä.

945
00:56:27,750 --> 00:56:31,480
Käyntiaika merge sort - meidän täytyy vain tapa puhua tästä.

946
00:56:31,480 --> 00:56:34,380
Tämä ei ole matematiikkaa, tämä on vain eräänlainen ytimekkään tapa ilmaista itseämme.

947
00:56:34,380 --> 00:56:39,080
Joten T edustaa aikaa ja n edustaa mitä? >> [Opiskelija] koko -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] koko ongelman, ihmisten määrä.

949
00:56:41,400 --> 00:56:45,470
Joten olen väittäen käyntiaika lajitella n ihmisiä tulee olemaan 0 aikaa

950
00:56:45,470 --> 00:56:50,290
jos n on pienempi kuin 2, koska jos sinulla on 1 kuppi tai no kupit, sinulla ei ole mitään lajitella.

951
00:56:50,290 --> 00:56:55,160
Mutta yleisemmin, aion ehdottaa, että käyntiaika lajitella n osia

952
00:56:55,160 --> 00:56:59,350
tulee olemaan se aika lajitella vasemmalle puoli plus oikea puoli

953
00:56:59,350 --> 00:57:03,110
plus - mitä tämä ylimääräinen + n? >> [Opiskelija] Merge sort.

954
00:57:03,110 --> 00:57:07,260
[Malan] Se on oikeastaan ​​sulautuvat, koska jos sinulla on n / 2 alkiota täällä

955
00:57:07,260 --> 00:57:11,500
ja sinulla on n / 2 alkiota täällä, kuinka paljon aikaa se kestää yhdistää ne?

956
00:57:11,500 --> 00:57:15,050
Aivan kuten Rob, sinun täytyy nyppiä tämä tänne, ehkä nyppiä tänne,

957
00:57:15,050 --> 00:57:17,120
nyppiä tänne, nyppiä tänne, katkomaan tänne.

958
00:57:17,120 --> 00:57:19,400
Sinun täytyy koskettaa jokaisen kupit kerran.

959
00:57:19,400 --> 00:57:22,030
Ja jos siellä on 4 kuppia ja 4 kupillista, eli 8 kupillista

960
00:57:22,030 --> 00:57:25,200
tai yleisemmin 8 N kuppia.

961
00:57:25,200 --> 00:57:28,470
Joten yhdistäminen askel voimme ilmaista kuin n,

962
00:57:28,470 --> 00:57:31,330
ja että kirjaimellisesti liittyy monta kertaa Rob fyysisesti kosketti

963
00:57:31,330 --> 00:57:33,410
yksi niistä Styrofoam kupit.

964
00:57:33,410 --> 00:57:35,850
Joten nyt tehdä mielivaltaisen esimerkin.

965
00:57:35,850 --> 00:57:41,850
Jos on 16 kuppia, mitä ajoaika lajittelu käyttäen Rob algoritmi, 16 kuppia?

966
00:57:41,850 --> 00:57:44,710
Se on 2 kertaa aikaa kuluu lajitella 8 kuppia

967
00:57:44,710 --> 00:57:46,920
koska meillä on 8 kuppia täällä, 8 kuppia täällä.

968
00:57:46,920 --> 00:57:51,520
En tiedä, kuinka kauan se kestää, joten olemme yleistäen sen t tällä hetkellä.

969
00:57:51,520 --> 00:57:53,320
Kuka tietää, mitä se on?

970
00:57:53,320 --> 00:57:58,990
Mutta nyt voin tavallaan rekursiivisesti tai toistuvasti kysyä saman kysymyksen.

971
00:57:58,990 --> 00:58:01,920
Kauanko kestää lajitella 8 kuppia?

972
00:58:01,920 --> 00:58:07,030
8 kupillista aion sanoa vie aikaa kuluu lajitella 4 kupillista plus 4 kuppia,

973
00:58:07,030 --> 00:58:08,880
sitten yhdistämällä ne yhteen.

974
00:58:08,880 --> 00:58:13,080
Hieno. Olemme joutumassa aikana jo. Kuinka kauan kestää lajitella 4 kupillista?

975
00:58:13,080 --> 00:58:19,150
Aika kuluu lajitella 4 kupillista on 2 kuppia plus 2 kuppia lajittelun lisäksi sulautuvien prosessia.

976
00:58:19,150 --> 00:58:21,440
Hieno. Kuinka kauan kestää lajitella 2 kuppia?

977
00:58:21,440 --> 00:58:26,290
2 kuppia on aikaa kuluu lajitella 1 kuppi plus aika kuluu lajitella toiseen kuppiin

978
00:58:26,290 --> 00:58:29,040
plus paljon aikaa se vie yhdistämistä, joka on vain 2.

979
00:58:29,040 --> 00:58:33,340
>> Hieno. Viimeinen kysymys. Kuinka kauan kestää lajitella 1 kuppi?

980
00:58:33,340 --> 00:58:37,260
Tässä on perusskenaariossa että ennustettu olimme osuma aiemmin.

981
00:58:37,260 --> 00:58:42,250
Se, että se ei ota työtä lainkaan lajitella pienin ongelmista

982
00:58:42,250 --> 00:58:44,120
tarkoittaa, että nyt tavallaan alakoulussa tyyli,

983
00:58:44,120 --> 00:58:46,460
voimme vain mennä aloittaa kytkemällä näitä numeroita takaisin sisään

984
00:58:46,460 --> 00:58:50,630
Tiedämme nyt, mitä T 1 on, niin voin kytkeä 0 T 1.

985
00:58:50,630 --> 00:58:54,420
Se antaa minulle vastaus T 2, jonka sitten voi kytkeä ylempänä.

986
00:58:54,420 --> 00:58:56,930
Se antaa minulle T 4, jonka voin kytkeä ylempänä.

987
00:58:56,930 --> 00:58:58,920
Se antaa minulle T 8, jonka voin kytkeä ylempänä.

988
00:58:58,920 --> 00:59:04,330
Ja jos minä itse tehdä, että matematiikka kytkemällä näitä vastauksia,

989
00:59:04,330 --> 00:59:08,590
Sitten saat T 16 on 64.

990
00:59:08,590 --> 00:59:12,090
Ja mitä 64 edustaa?

991
00:59:12,090 --> 00:59:15,700
Jos T on 16, joo, se on 16 kertaa 4.

992
00:59:15,700 --> 00:59:20,120
Olen siis väittävät nyt, että käyntiaika tämä asia sanottu yhdistää sort -

993
00:59:20,120 --> 00:59:22,590
ja tämä tulee olemaan fanciest ja niistä olemme nähneet tähän mennessä -

994
00:59:22,590 --> 00:59:26,160
aiotaan kutsutaan n log n

995
00:59:26,160 --> 00:59:31,140
sillä kuinka monta kertaa voi ryöstää jakaa koko joukko kupillista puoli? Log n.

996
00:59:31,140 --> 00:59:34,370
Se on sama kuin puhelinluettelon esimerkissä se on sama kuin itse laskenta esimerkin.

997
00:59:34,370 --> 00:59:36,380
>> Kuinka monta kertaa voit jakaa jotain puoli?

998
00:59:36,380 --> 00:59:38,410
Kuitenkin on olemassa tämä yhdistäminen askel.

999
00:59:38,410 --> 00:59:42,920
Saatat joutua jakaa kupit osaksi puoli uudestaan ​​ja uudestaan ​​ja uudestaan,

1000
00:59:42,920 --> 00:59:45,640
mutta joka kerta olet menossa täytyy yhdistää.

1001
00:59:45,640 --> 00:59:48,270
Ja me sanoimme aiemmin, että sulautuvan n kupit kestää n askelta

1002
00:59:48,270 --> 00:59:52,060
koska olet nyppiä pois cup, nyppiä pois kuppi, ja sinun täytyy koskettaa jokaista kuppi kerran,

1003
00:59:52,060 --> 00:59:53,510
aivan kuten Rob teki.

1004
00:59:53,510 --> 00:59:59,430
Eli jos teemme jotain log n kertaa ja teemme n asioita kunkin iteraation

1005
00:59:59,430 --> 01:00:03,090
jokainen näistä halvings, meillä on n kertaa log n.

1006
01:00:03,090 --> 01:00:07,220
Joten jos me kytkeä 16 tässä esimerkissä, 16 kertaa log 16 -

1007
01:00:07,220 --> 01:00:10,600
älä ole huolissasi, miksi näin on nyt, koska en ole kiinnittänyt Base -

1008
01:00:10,600 --> 01:00:16,100
mutta log pohjan 2 16 on 4, 16 kertaa 4 on 64.

1009
01:00:16,100 --> 01:00:22,350
Mutta sitä vastoin, jos olisimme käyttäneet kupla lajitella tai valinta lajitella tai lisäys lajitella kanssa 16 numeroa,

1010
01:00:22,350 --> 01:00:26,420
mitä käyntiaika on jos n on 16?

1011
01:00:26,420 --> 01:00:33,310
Se olisi 16 potenssiin, joka on 256, joka vaikka et ole aivan seurannut matematiikka,

1012
01:00:33,310 --> 01:00:38,390
256 on suurempi kuin 64. Se on todella maaginen takeaway täältä.

1013
01:00:38,390 --> 01:00:41,990
Ja ymmärtää, että työtä tällä pienissä esimerkeissä kun tahdon PSET

1014
01:00:41,990 --> 01:00:44,260
tekee kaiken paljon enemmän intuitiivinen.

1015
01:00:44,260 --> 01:00:49,070
Mutta mitä se oikeastaan ​​tarkoittaa kannalta tuntuu tämä algoritmi on tämä:

1016
01:00:49,070 --> 01:00:54,520
Jos me todella katsoa merge sort täällä - haluan vetää sitä tässä ikkunassa täällä -

1017
01:00:54,520 --> 01:00:58,560
Tämä on hieman erilainen esimerkki, jossa meillä on kaikki 3 näistä algoritmeista -

1018
01:00:58,560 --> 01:01:01,440
kupla, valinta, ja yhdistää - vain vierekkäin.

1019
01:01:01,440 --> 01:01:03,740
>> He ovat kaikki alkoi satunnainen baareja, ja se on hyvä.

1020
01:01:03,740 --> 01:01:06,240
Kukaan ei perustavanlaatuinen etu yli muiden.

1021
01:01:06,240 --> 01:01:09,500
Aion hetken napsauta jokaista näistä animaatioita - Käynnistä Start, Start -

1022
01:01:09,500 --> 01:01:13,270
niin nopeasti kuin voin siten, että karkeasti, ne kaikki alkavat samaan aikaan,

1023
01:01:13,270 --> 01:01:17,450
ja mennään mielestä kupla lajitella n Pahimmassa käyntiaika on mitä? >> [Opiskelija] N potenssiin.

1024
01:01:17,450 --> 01:01:21,560
N potenssiin. Valinta sort pahin tapaus käyntiaika on? N potenssiin.

1025
01:01:21,560 --> 01:01:25,150
Ja yhdistää sort on ilmeisesti - vaikka ei aivan noudata kaikkia matematiikka nyt,

1026
01:01:25,150 --> 01:01:30,610
siitä tulee paljon enemmän intuitiivinen ajan - on, väitämme, n kertaa log n.

1027
01:01:30,610 --> 01:01:35,210
Ja koska log n on ehdottomasti alle n. kerran meillä on suuria lukuja,

1028
01:01:35,210 --> 01:01:40,230
n kertaa log n on pienempi kuin n kertaa n tai n neliöön.

1029
01:01:40,230 --> 01:01:44,410
Joten mitä se tuntuu todella olla parempi algoritmi kannalta ajoaikaan,

1030
01:01:44,410 --> 01:01:50,380
n kertaa log n sijasta n neliö? Täällä mennään. Valitse, klik, klik.

1031
01:01:55,690 --> 01:01:58,650
>> Sitähän se tarkoittaa käyttää jotain merge sort.

1032
01:01:58,650 --> 01:02:01,680
Meillä on hetki. Katsotaan mitä tapahtuu täällä.

1033
01:02:09,440 --> 01:02:12,440
[Naurahtaa] Kenen rahaa on kupla lajitella?

1034
01:02:14,960 --> 01:02:16,730
Se pikemminkin riippuu tulon joskus.

1035
01:02:16,730 --> 01:02:18,120
Katsotaanpa.

1036
01:02:18,120 --> 01:02:23,320
Tule. Tuntuu kuin hän kiinni. >> [Opiskelija] Mene, kupla lajitella!

1037
01:02:23,320 --> 01:02:27,370
[Opiskelijat sorinaa]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Joo, joo.

1039
01:02:29,120 --> 01:02:34,520
[Opiskelijat sorinaa] Mene, mene, mene!

1040
01:02:37,210 --> 01:02:40,450
[Kaikki hurraavat] [aplodit]

1041
01:02:40,450 --> 01:02:46,240
Joten nyt 1 viimeinen, lopullinen demo, jos se on vähän hankala wrap mieltäsi noin matematiikka

1042
01:02:46,240 --> 01:02:49,280
tai tavallaan visualisoinnin siellä, voit itse kuulla nopeudet

1043
01:02:49,280 --> 01:02:51,000
eri algoritmien eri tavoin.

1044
01:02:51,000 --> 01:02:53,900
Tämä on animaatio joku teki tosiasiallisesti yhdistää kuulostaa

1045
01:02:53,900 --> 01:02:56,980
prosessin vaihtava ja korkeus baareissa.

1046
01:02:56,980 --> 01:03:00,440
Kuten näemme täällä, siellä on muutama enemmän lajittelualgoritmeja siellä, että ihmiset ovat ajatelleet.

1047
01:03:00,440 --> 01:03:03,660
Tämä ensimmäinen tulee olemaan lisäys lajitella, ja tämä lentää läpi

1048
01:03:03,660 --> 01:03:07,090
ja antaa sinulle kuultavissa tunteen siitä, miten nämä eri algoritmeja työtä.

1049
01:03:07,090 --> 01:03:09,080
Tässä on lisäys tavallaan.

1050
01:03:09,080 --> 01:03:18,410
[Elektroninen merkkiäänen]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Nopeampi sähköinen piippaus]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Selection sort.

1054
01:03:48,950 --> 01:04:03,580
[Nopeampi sähköinen piippaus]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge sort.

1056
01:04:05,770 --> 01:04:17,270
[Elektroninen merkkiäänen]

1057
01:04:17,270 --> 01:04:20,180
[Merkkiäänen hidastaa] [naurua]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome tavallaan.

1059
01:04:22,590 --> 01:04:38,580
[Elektroninen merkkiäänen]

1060
01:04:39,740 --> 01:04:46,150
>> Tämä on CS50. Nähdään ensi viikolla. [Aplodit ja hurraavat]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]