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

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Sveučilište Harvard]

3
00:00:04,110 --> 00:00:07,130
>> [Ovo je CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> U redu. Dobrodošao natrag. Ovo je CS50 i to je kraj tjedna 3.

5
00:00:11,010 --> 00:00:14,680
>> Dakle, za one koji nisu upoznati, prošle godine Harvardu pokrenuo ono što se zove Innovation laboratorij,

6
00:00:14,680 --> 00:00:18,530
ili ja-laboratorij, koji je prekrasan zgrada preko rijeke APK kampusu

7
00:00:18,530 --> 00:00:22,640
koji je otvoren za studente, učenike, studente GSAS iz diljem kampusa,

8
00:00:22,640 --> 00:00:27,000
uključujući profesore, i to je mjesto da se zajedno raditi na inovativnim stvarima,

9
00:00:27,000 --> 00:00:29,180
posebno poduzetničkih stvari

10
00:00:29,180 --> 00:00:33,410
ako i 0 ili više prijatelja misleći da radiš nešto poduzetničke

11
00:00:33,410 --> 00:00:37,080
bilo tijekom ove klase, nakon ove klase, ili izvan nje.

12
00:00:37,080 --> 00:00:41,540
>> Dakle, jedna od stvari koje rade preko J pojma ti izlete,

13
00:00:41,540 --> 00:00:44,510
od kojih je jedan u New Yorku, jedna od kojih je u Silicijskoj dolini.

14
00:00:44,510 --> 00:00:47,530
Prostor je vrlo ograničen, ali to je prilika da se trljati ramenima s mbas

15
00:00:47,530 --> 00:00:52,200
i diplomirani studenti diljem kampusa, a zapravo provesti vrijeme u tim područjima za

16
00:00:52,200 --> 00:00:55,500
razgovor se startupima, pričajući poduzetnicima i slično.

17
00:00:55,500 --> 00:00:57,870
Dakle, ako je zainteresiran, provjeriti ovaj URL ovdje.

18
00:00:57,870 --> 00:01:01,220
To je također dostupan na slajdovima online.

19
00:01:01,220 --> 00:01:04,610
>> Možemo ton dolje kuću audio samo malo?

20
00:01:04,610 --> 00:01:08,640
Ako želite da nam se pridružite za ručak ovaj petak, 13:15 u Fire & Ice, molimo glavu tamo.

21
00:01:08,640 --> 00:01:11,390
Isprike ako oblik već ispunjen u vrijeme kada se tamo.

22
00:01:11,390 --> 00:01:13,750
No, mi ćemo nastaviti ovu tradiciju naprijed.

23
00:01:13,750 --> 00:01:17,350
>> Danas ćemo nastaviti višu razinu rasprave o raznim problemima koje možemo riješiti,

24
00:01:17,350 --> 00:01:21,330
fokusirajući se puno manje, barem danas, na broj i još mnogo toga o idejama.

25
00:01:21,330 --> 00:01:24,720
Dakle, mislim natrag na tjedan 0 kad smo poderali telefonski imenik na pola,

26
00:01:24,720 --> 00:01:28,260
Cilj koji je bio nešto učiniti, doduše, malo dramatična

27
00:01:28,260 --> 00:01:32,360
ali poslati točku da traženje ne mora biti nužno,

28
00:01:32,360 --> 00:01:35,100
kao očigledan na prvi pogled, kao što možda mislite.

29
00:01:35,100 --> 00:01:40,200
A rješavanje problema u cjelini ne mora nužno može uvijek biti najbolji -

30
00:01:40,200 --> 00:01:44,130
Najočitiji rješenje ne mora nužno može biti najbolji.

31
00:01:44,130 --> 00:01:47,300
Dakle, imali smo tu telefonski imenik i, iskreno, sve nas u ovoj sobi imali instinkte,

32
00:01:47,300 --> 00:01:51,470
najvjerojatnije, početi u sredini kada je u potrazi za Mike Smith i onda ići lijevo ili desno

33
00:01:51,470 --> 00:01:54,280
temelji se na bilo slovo abecede mi se dogodilo da se na kraju.

34
00:01:54,280 --> 00:01:57,560
>> Ali to jednostavna ideja da smo mi ljudi uzima zdravo za gotovo tako dugo

35
00:01:57,560 --> 00:02:00,670
stvarno trebali početi dolaziti na čelu svoje pameti

36
00:02:00,670 --> 00:02:03,900
jer kao što su problemi dobiti mnogo složeniji od telefonskog imenika,

37
00:02:03,900 --> 00:02:07,420
one iste jednostavne, sjajne uvidi što će omogućiti nam

38
00:02:07,420 --> 00:02:10,259
riješiti mnogo složeniji i zanimljiviji problema,

39
00:02:10,259 --> 00:02:12,930
među njima neke stvari uzimamo zdravo za gotovo već ovih dana.

40
00:02:12,930 --> 00:02:15,720
Milijarde web stranice vani, i još Google i Bing i kao

41
00:02:15,720 --> 00:02:17,660
su u stanju pronaći stvari za nas kao da.

42
00:02:17,660 --> 00:02:22,300
To se ne događa pomoću linearne pretraživanje, traži kroz sve moguće web stranicama.

43
00:02:22,300 --> 00:02:25,290
Facebook je u mogućnosti da vam reći tko je sve od vaših prijatelja ili prijatelji prijatelja,

44
00:02:25,290 --> 00:02:28,250
i da previše može učiniti naizgled u trenu ovih dana

45
00:02:28,250 --> 00:02:30,820
iako imaju milijune korisnika.

46
00:02:30,820 --> 00:02:34,250
>> I tako kako smo zapravo riješiti probleme na toj skali će u konačnici smanjiti

47
00:02:34,250 --> 00:02:37,830
s idejama smo gledali u tjednu 0 i danas malo više.

48
00:02:37,830 --> 00:02:42,320
Nećemo ponovo izvršiti ovaj algoritam, ali sjećam se također učinili u tjednu 0 Ova vježba

49
00:02:42,320 --> 00:02:44,780
gdje smo svi ustanu, uzeti na broju 1,

50
00:02:44,780 --> 00:02:48,720
i onda smo imali sve self-count po uparivanje off, dodajući svoje brojeve zajedno,

51
00:02:48,720 --> 00:02:51,930
tada polovica bande sjeo na svakom iteracija.

52
00:02:51,930 --> 00:02:56,750
Tako smo išli od 500 studenata na 250-125 i tako dalje.

53
00:02:56,750 --> 00:03:00,080
No, kao što smo rekli u ponedjeljak, moćna ideja postoji

54
00:03:00,080 --> 00:03:02,460
je da, ako smo udvostručili veličinu tog problema

55
00:03:02,460 --> 00:03:06,480
i sva djeca iz pravosuđa ili EC 10 se vratio u sobu i pridružio nam se,

56
00:03:06,480 --> 00:03:09,510
dobro, vjerojatno nije mogao računati da cijeli agregat grupu

57
00:03:09,510 --> 00:03:13,380
sa samo jednom više velikih iteracija petlje jer bi samo možda udvostručiti veličinu

58
00:03:13,380 --> 00:03:15,630
ili u EZ 10 slučaju malo više nego dvostruko u veličini.

59
00:03:15,630 --> 00:03:18,440
I tako ćemo morati potrošiti malo više vremena,

60
00:03:18,440 --> 00:03:22,000
ali mi ne bi trebali potrošiti 400 ili 700 više koraka.

61
00:03:22,000 --> 00:03:26,550
>> Samo slikati ovu sliku na način koji je malo manje apstraktno, nemojmo su svi ustanu.

62
00:03:26,550 --> 00:03:31,100
Ali, ako one od vas koji su odabrali da sjedi u orkestru danas ne bi smetalo stojeći,

63
00:03:31,100 --> 00:03:34,580
neka je vidjeti ako možemo shvatiti među vama koji najviša osoba

64
00:03:34,580 --> 00:03:36,730
obavljajući istu vrstu komparativne algoritma.

65
00:03:36,730 --> 00:03:41,830
Dakle, ako ste sjedi u orkestru, moje isprike, ali korak 1, stand up;

66
00:03:41,830 --> 00:03:44,650
2. korak, par off s kim ste u blizini,

67
00:03:44,650 --> 00:03:49,360
shvatiti tko je jači, i sjesti ako su kraći.

68
00:03:49,360 --> 00:03:51,360
Zatim ponovite.

69
00:03:51,360 --> 00:03:56,280
[Studenti mrmljajući]

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

71
00:04:15,320 --> 00:04:19,010
Ok. Jedan je napustio položaj. Koje je vaše ime? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrija, ti si najviši osoba u orkestru sekciji danas.

73
00:04:21,959 --> 00:04:28,100
>> Čestitamo. [Pljesak i navijanje] Ok. Imati sjedište. Dakle, našli smo Andriju.

74
00:04:28,100 --> 00:04:30,870
No, koliko dugo će to su me uzeti, na primjer, kako bi pronašli Andriju

75
00:04:30,870 --> 00:04:33,740
u ovom orkestru dijelu 50 + ili tako ljudi?

76
00:04:33,740 --> 00:04:36,900
Mogao sam uzeti prilično jednostavan pristup i početi ovdje.

77
00:04:36,900 --> 00:04:39,270
I ja sam 2 ljudi ustanu i samo sam ih usporediti,

78
00:04:39,270 --> 00:04:42,120
i onda ja kažem da onaj tko je nešto kraća, "Ok, ti ​​sjedni"

79
00:04:42,120 --> 00:04:44,380
i ja ću se sjetiti tko jači osoba bila.

80
00:04:44,380 --> 00:04:49,030
Tada sam, ponavljam, ponavljam, ponavljam, i ja objesiti na najvišim osobi

81
00:04:49,030 --> 00:04:51,920
dok sam naći netko nešto viši od njih, na kojem trenutku

82
00:04:51,920 --> 00:04:54,950
nešto kraći osoba ima onda sjesti.

83
00:04:54,950 --> 00:04:57,690
No, u tom algoritmu u ovom dijelu orkestra, ako postoji n od vas,

84
00:04:57,690 --> 00:05:00,480
koliko koraka je da algoritam će to trajati? >> [Student] N.

85
00:05:00,480 --> 00:05:03,580
>> To će potrajati n, desno, jer u najgorem slučaju, da se tako izrazim,

86
00:05:03,580 --> 00:05:09,090
najviša osoba je vrlo posljednja osoba da ću dobiti samo slučajnim peh.

87
00:05:09,090 --> 00:05:14,260
Dakle, u najgorem slučaju, trajanje tog algoritma je linearno, to je n

88
00:05:14,260 --> 00:05:18,070
gdje je n je ukupan broj ljudi u prostoru, veličina problema.

89
00:05:18,070 --> 00:05:19,600
Što o tom algoritmu?

90
00:05:19,600 --> 00:05:22,080
Činjenica da ste svi ustali i onda opet pola vas sjeo,

91
00:05:22,080 --> 00:05:23,950
pola vas sjeo, pola od vas sjeo.

92
00:05:23,950 --> 00:05:26,070
Koliko koraka treba da su se, ako postoji n od vas ovdje?

93
00:05:26,070 --> 00:05:30,200
[Student] N log n. >> To bi bilo još gore. Prijavite n.

94
00:05:30,200 --> 00:05:32,930
>> Dakle, prijavite n, čak i ako ne sasvim sjetiti što je logaritam,

95
00:05:32,930 --> 00:05:38,410
za sada, samo cijenim da se odnosi na neki način to prepoloviti i prepoloviti i prepoloviti.

96
00:05:38,410 --> 00:05:41,000
To ne mora biti faktor dva. To bi mogla biti čimbenik tri.

97
00:05:41,000 --> 00:05:46,560
No, to je to ponavljanje iste vrste faktora tako da je veličina problem počinje ovdje

98
00:05:46,560 --> 00:05:49,620
ali onda odmah ide ovdje, onda ovdje, onda ovdje, onda ovdje.

99
00:05:49,620 --> 00:05:53,580
Vi ne uzimate male bites iz problema, ste stvarno sjeckanje daleko na njega

100
00:05:53,580 --> 00:05:56,160
s velikim naletu svaki put.

101
00:05:56,160 --> 00:06:00,810
Tako smo imali 50 ljudi, zatim 25, pa 12 ½ ili 13 ljudi stoji,

102
00:06:00,810 --> 00:06:05,370
onda 6 ½ i tako dalje dok napokon samo Andrew je ostao stajati.

103
00:06:05,370 --> 00:06:08,710
Tako ćemo nazvati taj zapisnik n, a možete vizualizirati ovo što slijedi.

104
00:06:08,710 --> 00:06:12,570
Podsjetimo ovu sliku ovdje gdje linearni algoritam je poput crvene linije tamo,

105
00:06:12,570 --> 00:06:17,520
žuta linija bila brojanje prema 2s algoritam koji smo koristili za brojanje studente

106
00:06:17,520 --> 00:06:22,300
u prošlosti, ali danas je sveti gral će ostati ova zelena linija

107
00:06:22,300 --> 00:06:25,470
gdje ako smo udvostručili broj ljudi u orkestru sekciji ili jednostavno rekao,

108
00:06:25,470 --> 00:06:29,170
kvragu, ajmo se svi u cijeloj sobi stand up, a ne kao velika stvar

109
00:06:29,170 --> 00:06:31,560
jer smo otprilike dvostruko koliko su ljudi ovdje dolje,

110
00:06:31,560 --> 00:06:33,500
1 više iteracija, nije problem.

111
00:06:33,500 --> 00:06:36,200
>> Našli smo Andrija ili tko se događa da se jači nego Andrija

112
00:06:36,200 --> 00:06:38,770
u polukatu ili balkona.

113
00:06:38,770 --> 00:06:42,140
Dakle, ove jednostavne ideje da mi je uzeo toliko zdravo za gotovo u telefonskom imeniku,

114
00:06:42,140 --> 00:06:46,170
shvatiti da postoji toliko različitih mjesta u kojem možemo ga primijeniti.

115
00:06:46,170 --> 00:06:50,810
Samo slap neke žargon - Zapravo, nego žargon prvi,

116
00:06:50,810 --> 00:06:52,750
pusti me na ovu sliku ovdje.

117
00:06:52,750 --> 00:06:56,970
Upravo sada smo govorili o n i n / 2, a zatim se prijavite n,

118
00:06:56,970 --> 00:07:00,500
ali svakako može doći do, kako ćemo tijekom semestra,

119
00:07:00,500 --> 00:07:05,130
druga vrsta matematičkih formula opisati ovaj opći pojam o prikazivati ​​vrijeme.

120
00:07:05,130 --> 00:07:07,580
To su iz konteksta za sada, jer ćemo vidjeti zadugo

121
00:07:07,580 --> 00:07:09,900
algoritmi koji to zapravo predstavljaju.

122
00:07:09,900 --> 00:07:17,990
>> Ali primijetite ovdje linearna linija N, ravna crta, je zapravo vrlo niska pokazuje upravo sada.

123
00:07:17,990 --> 00:07:22,950
To je svojevrsna optička varka u koji smo samo promijeniti ono što os x predstavlja

124
00:07:22,950 --> 00:07:26,130
i y osi, a mi možemo napraviti ravne linije točku u bilo kojem smjeru želimo.

125
00:07:26,130 --> 00:07:30,350
No, razlog da je tako naizgled stan sada

126
00:07:30,350 --> 00:07:35,690
je zato što mi je potrebno da bi boravkom na ovom grafu za mnogo sporije trčanje vremena.

127
00:07:35,690 --> 00:07:39,030
Za sada, znam da postoje neke prilično loše algoritmi u životu,

128
00:07:39,030 --> 00:07:43,790
od kojih su neki ne uzimaju n korake ili, još bolje, prijavite n korake, ali više.

129
00:07:43,790 --> 00:07:48,820
Dakle, iznad crte n ovdje na dnu obavijesti tu je n puta log n,

130
00:07:48,820 --> 00:07:51,410
pa ćemo vidjeti što to znači prije dugo.

131
00:07:51,410 --> 00:07:56,010
Iznad da je n kvadratna, a nismo vidjeli nikakve n kvadratnih algoritme, ali još smo uskoro.

132
00:07:56,010 --> 00:07:57,660
I to izgleda jako loše.

133
00:07:57,660 --> 00:08:01,610
Tu je 2 do n, nešto eksponencijalna, koja se osjeća još gore.

134
00:08:01,610 --> 00:08:05,760
Pa ipak, začudo, onda postoji n kubu, koji, ako ste vrsta razmišljanja naprijed,

135
00:08:05,760 --> 00:08:10,000
ako vrsta učiniti math, 2 do n zapravo postaje puno ravniji,

136
00:08:10,000 --> 00:08:15,930
mnogo viši nego n kubu ako pogledate osi dovoljno daleko van.

137
00:08:15,930 --> 00:08:19,890
Dakle primijetiti upravo sada ove osi samovoljno 2 do 10 na x osi.

138
00:08:19,890 --> 00:08:21,770
>> A što to znači?

139
00:08:21,770 --> 00:08:23,890
To znači da dvije ljudi do 10 ljudi u sobi.

140
00:08:23,890 --> 00:08:27,200
To je sve x znači: veličina problema, bez obzira na kontekst.

141
00:08:27,200 --> 00:08:30,420
I vertikalna os upravo sada je broj sekundi ili broj koraka -

142
00:08:30,420 --> 00:08:31,840
neki jedinica vremena.

143
00:08:31,840 --> 00:08:34,740
Ali primijetite da je 0-60 i 0-10.

144
00:08:34,740 --> 00:08:38,549
Ali ako ćemo vrsta zoom out, kao možda u Excelu ili nekom crtati softver,

145
00:08:38,549 --> 00:08:43,370
i idemo do 200.000, primijetiti da nešto poput 2 do n

146
00:08:43,370 --> 00:08:47,520
će u potpunosti preplaviti pokrenute puta od n kvadrata,

147
00:08:47,520 --> 00:08:50,960
n kubu, n log n - sve smo razgovarali o do sada.

148
00:08:50,960 --> 00:08:54,190
A ipak, ulov je kada početi govoriti o stvarima kao što su Facebook

149
00:08:54,190 --> 00:08:57,150
gdje ste mnogo, mnogo, mnogo ljudi svi međusobno povezani,

150
00:08:57,150 --> 00:09:00,650
ste n ljudi, od kojih svaki može imati koliko god n prijatelja

151
00:09:00,650 --> 00:09:02,860
ako svatko je vrsta ortak u svijetu,

152
00:09:02,860 --> 00:09:08,100
dobro, to je n puta n već, tako da je n kvadratnih moguće prijateljstva,

153
00:09:08,100 --> 00:09:10,950
barem u 1 smjeru, n kvadratna mogućih prijateljstava.

154
00:09:10,950 --> 00:09:15,330
Tako da je već sugerira da traži facebook društveni graf, da se tako izrazim,

155
00:09:15,330 --> 00:09:18,090
može početi da se izražava u takvim formulama.

156
00:09:18,090 --> 00:09:19,820
>> Vratit ćemo i učiniti ovo puno konkretniji,

157
00:09:19,820 --> 00:09:23,280
ali za sada, cilj za narednih nekoliko tjedana

158
00:09:23,280 --> 00:09:27,170
će biti sigurni da neće ići o provedbenim algoritama ili kod

159
00:09:27,170 --> 00:09:29,870
da kraj gore uzimajući onoliko vremena kao nešto poput ovoga.

160
00:09:29,870 --> 00:09:33,110
Ali fascinantna stvar o informatici ako nastavi u ovom području

161
00:09:33,110 --> 00:09:38,320
uzimanje nastavu kao CS121, CS124, od kojih su oba teorija tečajevi,

162
00:09:38,320 --> 00:09:41,300
je da zapravo postoje neki problemi koji postoje na ovom svijetu

163
00:09:41,300 --> 00:09:45,710
koje iz temelja, koliko znamo, ne može riješiti bilo brže

164
00:09:45,710 --> 00:09:48,880
od najgore od tih grafova zapravo sugerira.

165
00:09:48,880 --> 00:09:53,660
Dakle, tu je puno otvorenih problema u ovom svijetu da to puno bolje nego ljudi imaju tako daleko.

166
00:09:53,660 --> 00:09:56,130
>> Pa krenimo onda sa ovom primjeru.

167
00:09:56,130 --> 00:09:59,650
Vidjeli smo Sean borbu s tom na kameri, sve previše neprilično na videu.

168
00:09:59,650 --> 00:10:05,270
No, stvarnost je kad Sean je zadatak pronaći na brodu kao što je ovaj broj 7,

169
00:10:05,270 --> 00:10:10,300
Podsjetimo da sam rekao da, "Tu je negdje iza tih komada papira ili bijelih vrata

170
00:10:10,300 --> 00:10:12,570
"Broj 7. Sean ga pronaći za nas."

171
00:10:12,570 --> 00:10:14,200
I to je predivno neugodno gledati

172
00:10:14,200 --> 00:10:15,790
jer je on bio stvarno bore s ovim problemom.

173
00:10:15,790 --> 00:10:19,720
No, stvarnost je Sean činio kao netko u sobi mogao imati učinjeno.

174
00:10:19,720 --> 00:10:21,890
Uzeo je malo duže nego tipična osoba može imati,

175
00:10:21,890 --> 00:10:24,760
ali on pretpostavlja da je bio neki trik za ovaj problem,

176
00:10:24,760 --> 00:10:26,590
on pretpostavlja da je bio nešto nedostaje.

177
00:10:26,590 --> 00:10:29,320
I to nije pomoglo da se stotine oči su imajući dolje na njega.

178
00:10:29,320 --> 00:10:34,250
>> No, stvarnost je da je ulaz na problem je hrpa slučajnih brojeva

179
00:10:34,250 --> 00:10:37,120
a vi ste se pitali kako pronaći jedan takav broj,

180
00:10:37,120 --> 00:10:39,770
Najbolje što možete učiniti je linearno pretraživanje.

181
00:10:39,770 --> 00:10:44,060
Start na lijevoj strani, premjestiti na desno, ili početi na desno, premjestiti na lijevoj strani.

182
00:10:44,060 --> 00:10:48,300
Retroaktivno, mogli bismo biti razmišljanje ", Sean, zašto nisi samo početi s drugog kraja?"

183
00:10:48,300 --> 00:10:52,120
Pa, 7 je mogao samo tako lako je ovdje slučajno,

184
00:10:52,120 --> 00:10:54,980
ali namjerno sam ga stavio tamo jer sam shvatio da se neće početi krajem.

185
00:10:54,980 --> 00:10:59,320
Tako sam nekako manipulira situaciju, ali Slučajnost 7 mogao biti bilo gdje.

186
00:10:59,320 --> 00:11:02,380
Dakle, počevši od desnog kraja možda bilo bolje onda,

187
00:11:02,380 --> 00:11:04,320
ali što ako iduće godine selim 7 drugdje?

188
00:11:04,320 --> 00:11:06,830
To nije temeljno novo rješenje za problem -

189
00:11:06,830 --> 00:11:10,520
počevši od jednog kraja ili druge - kada si dao nema druge pretpostavke.

190
00:11:10,520 --> 00:11:13,620
Dakle, Sean počeo u potrazi kroz brojeva i on je rekao, "5. To nije ovdje."

191
00:11:13,620 --> 00:11:17,280
Tada je otišao ovdje i vidio 19, a zatim je zastao za oko 20 sekundi,

192
00:11:17,280 --> 00:11:22,330
onda je otvorio to za 13, a onda je postalo očito

193
00:11:22,330 --> 00:11:24,270
da ne izgleda kao da se obrazac ovdje.

194
00:11:24,270 --> 00:11:28,090
To nije 1, 2, 3, 4 ili slično. Tu su praznine u brojkama, koje nije pomoglo.

195
00:11:28,090 --> 00:11:32,320
I također, činjenica da sam koristio ove jeftine komada papira da prikrije brojeve

196
00:11:32,320 --> 00:11:35,270
je zapravo namjerno, jer ako sam uklonio sve ove komada papira,

197
00:11:35,270 --> 00:11:38,760
većina nas, Sean uključeni, vjerojatno bi pogledao vrsta makroskopski

198
00:11:38,760 --> 00:11:43,410
na ploči i rekao: "Oh, 7 je očito tamo." Učinili smo to odmah.

199
00:11:43,410 --> 00:11:46,460
>> I to može biti način ljudski mozak funkcionira u određenoj mjeri,

200
00:11:46,460 --> 00:11:50,730
ali u stvarnosti, oči ili um je vjerojatno skimming brojeve s desna na lijevo,

201
00:11:50,730 --> 00:11:55,190
s lijeva na desno, srednji na van - nešto se događa fiziološki

202
00:11:55,190 --> 00:11:57,640
kao da se osjećao kao da se događa odmah,

203
00:11:57,640 --> 00:12:01,360
ali izgledi su čak i interno tamo bila neka vrsta metodologije za pronalaženje 7.

204
00:12:01,360 --> 00:12:05,160
I doista, sad kad govorimo o nizovima i struktura podataka

205
00:12:05,160 --> 00:12:08,780
i memorija unutar računala, jedino mi ljudi mogu učiniti

206
00:12:08,780 --> 00:12:13,070
je pogledati na pojedinim mjestima memorijskih jednom na vrijeme.

207
00:12:13,070 --> 00:12:16,600
>> Dakle, svaki drugi položaj kao što bi i biti pokriven s nekom papiru

208
00:12:16,600 --> 00:12:21,170
jer ne možemo ga vidjeti u svakom slučaju. Mi možemo učiniti samo jedna stvar u isto vrijeme.

209
00:12:21,170 --> 00:12:25,030
Dakle, u ovom slučaju, u Sean slučaju, otišli smo ovdje i onda smo otišli ovdje

210
00:12:25,030 --> 00:12:31,040
i onda smo otišli ovdje, ovdje, ovdje, ovdje, dobio pametan do kraja

211
00:12:31,040 --> 00:12:34,450
i samo vrsta preskočila ovaj jedan samovoljno i pronašao 7 tamo.

212
00:12:34,450 --> 00:12:37,470
Ovo nije bio osobito posebna. To je također bio iz reda.

213
00:12:37,470 --> 00:12:39,530
No, on je konačno pronašao 7.

214
00:12:39,530 --> 00:12:45,360
Ali sada takeaway stvarno je to najbolje što možete učiniti kada je dobio nikakvu informaciju

215
00:12:45,360 --> 00:12:50,400
osim nasumično poredani brojeva je početi s lijeve ili započeti s desne strane.

216
00:12:50,400 --> 00:12:54,950
Ili pakao, da slučajno može otvoriti vrata, ali čak i tada ono što to znači biti slučajan?

217
00:12:54,950 --> 00:12:57,220
Pa, mi bismo se nekako formalizirati što to znači za početak ovdje,

218
00:12:57,220 --> 00:13:01,150
onda ići ovdje, onda ići ovdje. Sean je velik, a to je bio samo zabavno gledati.

219
00:13:01,150 --> 00:13:06,340
Što ako umjesto toga smo promijenili je problem malo i dovesti do ovogodišnjeg Seana, ako hoćeš?

220
00:13:06,340 --> 00:13:09,460
Bi li itko biti udoban dolazi na pozornicu i rješavanju malo drugačiji problem

221
00:13:09,460 --> 00:13:12,330
i koji se pojavljuju na kameru?

222
00:13:12,330 --> 00:13:15,720
>> Idemo dalje orkestra, jer ti dečki su prilično uključeni već danas.

223
00:13:15,720 --> 00:13:21,430
Kako o u ružičasto, u šeširu? Dođite na dolje. Koje je vaše ime? >> Alex. >> Alex. Ok.

224
00:13:21,430 --> 00:13:24,580
Dakle, Alex će biti ovogodišnji Sean i pojavit će se u narednih nekoliko godina

225
00:13:24,580 --> 00:13:27,770
vrijedan CS50 predavanja.

226
00:13:27,770 --> 00:13:30,340
Alex, lijepo da zadovolji vas. >> Drago previše.

227
00:13:30,340 --> 00:13:33,470
Izazov pri ruci za vas je da ste ga malo lakše

228
00:13:33,470 --> 00:13:38,950
u da kažem vam iste brojeve ovdje, ali oni su sada riješeno.

229
00:13:38,950 --> 00:13:41,800
Tako sada vaš cilj je pronaći broj sedam.

230
00:13:41,800 --> 00:13:45,370
A zapravo, mi stvarno treba napraviti ovo - ti si vrste varanja, kao i računalo ne bi,

231
00:13:45,370 --> 00:13:47,990
gleda na ono što su brojevi bili maloprije.

232
00:13:47,990 --> 00:13:50,360
S kredom to zapravo ne ide kako bi se sve to puno,

233
00:13:50,360 --> 00:13:52,810
ali ajmo se pretvarati da ne znate što je izvorni polje je.

234
00:13:52,810 --> 00:13:56,600
Sve što sada znamo je da imate niz sortirani brojeva

235
00:13:56,600 --> 00:14:00,360
koji bi mogli imati praznine između njih, i vaš cilj je pronaći broj sedam.

236
00:14:00,360 --> 00:14:05,080
Kako bi ste, razuman čovjek, ići o pronalaženju broj 7?

237
00:14:05,080 --> 00:14:07,770
>> Idi od niske do visoke? >> Ok. Idi niske do visoke.

238
00:14:07,770 --> 00:14:10,990
I nemojte ih otkinuti. Ajmo ih podignite tako da ih možemo ponovno.

239
00:14:10,990 --> 00:14:14,730
Dobro, 1. Čekaj. Prije nego što dalje, to je bio jedan, jasno krivu.

240
00:14:14,730 --> 00:14:17,270
Dakle, ono što se događa kroz vaš um sljedeći? Što je vaš sljedeći potez?

241
00:14:17,270 --> 00:14:23,250
Sljedeći. >> Ok. Sljedeći. Dobar. 3, tako netočne. Što je vaš sljedeći potez?

242
00:14:23,250 --> 00:14:27,670
Imajte na idući. >> Redu. Imajte na idući. 5.

243
00:14:27,670 --> 00:14:31,110
Dakle, držati na idući, i neka mi ruka ti ovo za buduće naraštaje.

244
00:14:31,110 --> 00:14:35,720
7. >> Izvrsno. Vrlo dobro. Pronađeno broj sedam. [Pljesak]

245
00:14:35,720 --> 00:14:39,720
Dakle, ono što je dobro, ali Sean previše pronašao broj sedam.

246
00:14:39,720 --> 00:14:44,490
I tvrdim da niste stvarno iskoristiti ovaj dodatni dio informacija,

247
00:14:44,490 --> 00:14:47,780
a to je da su ti brojevi sortiraju.

248
00:14:47,780 --> 00:14:51,520
Dakle, možemo učiniti bolje? Bilo koji sugestija ovdje? Da, u leđa.

249
00:14:51,520 --> 00:14:54,710
[Student] Binarni pretraživanje. >> Nemam pojma što binarno pretraživanje je.

250
00:14:54,710 --> 00:14:58,030
>> [Student] Početak u sredini. >> Početak u sredini. Ok. Dakle, neka je vidjeti ako možemo doći.

251
00:14:58,030 --> 00:15:02,580
Dakle, ako umjesto da ste rekli početi od sredine, ići naprijed i otvoriti srednju vrata.

252
00:15:02,580 --> 00:15:04,580
Tu je osam od njih, tako da ćete morati proizvoljno odabrati jedan

253
00:15:04,580 --> 00:15:09,800
malo na lijevo ili na desno. Ok. 7! [Pljesak] Jako lijepo.

254
00:15:09,800 --> 00:15:11,410
Ok, ali gdje su mi ide s tim?

255
00:15:11,410 --> 00:15:14,990
Pretpostavimo samo razbiti kravatu što je počeo ovdje

256
00:15:14,990 --> 00:15:16,670
jer je to jednako moglo dogoditi, kao dobro.

257
00:15:16,670 --> 00:15:19,540
Mi se upravo dogodilo da znaju da je 7 bio tamo. Dakle, ovo je 13.

258
00:15:19,540 --> 00:15:21,980
Dakle, ako su razvrstani i samo smo započeli u sredini,

259
00:15:21,980 --> 00:15:24,600
što bi optimalno sljedeći potez bio?

260
00:15:24,600 --> 00:15:27,740
Idi lijevo. I tako evo primjer telefonskog imenika opet.

261
00:15:27,740 --> 00:15:30,130
Ako 13 je ovdje i znamo popis sortiran,

262
00:15:30,130 --> 00:15:33,900
onda sve od tih komada papira su nezanimljivo za nas sada

263
00:15:33,900 --> 00:15:37,400
jer smo već znali da sedam mora biti lijevo

264
00:15:37,400 --> 00:15:39,510
ako su ti brojevi sortiraju i našli smo 13.

265
00:15:39,510 --> 00:15:42,500
>> Dakle, ono što je vaš sljedeći potez ovdje? >> Idite na lijevoj strani. >> Dobro, dobro.

266
00:15:42,500 --> 00:15:45,080
Dakle, idite na lijevo, i - čekati, hej, hej, hej. To je varanje.

267
00:15:47,140 --> 00:15:51,350
Tako ste pronašli sedam, ali ono što je algoritam mi samo primijeniti?

268
00:15:51,350 --> 00:15:56,450
Počnite u sredini. >> Dobro. Dakle, ono što je logičan nastavak te iste ideje?

269
00:15:56,450 --> 00:15:58,970
Oh, samo to. >> Točno. >> Tako sam početi ovdje. >> Dobro.

270
00:15:58,970 --> 00:16:02,020
Dakle, sada smo otišli malo na lijevo ponovno. To je tri.

271
00:16:02,020 --> 00:16:05,310
No, zanimljivo takeaway sada je što neki to ne morate brinuti o?

272
00:16:05,310 --> 00:16:08,040
Ovo dvoje. >> Ovo dvoje. Dakle, sada to može ići dalje, to se može otići.

273
00:16:08,040 --> 00:16:12,330
Sada je problem da je 8 onda je veličina 4 sada je veličine 2.

274
00:16:12,330 --> 00:16:16,430
Mi smo uzimajući prilično blizak. Opet, idite na sredini tih dvaju elemenata.

275
00:16:16,430 --> 00:16:20,430
>> Ok. Dakle, to je vrsta nesretni da sada smo uvijek ide lijevo, jer smo zaokruživanje dolje.

276
00:16:20,430 --> 00:16:25,150
Ali to je u redu jer se sada bacamo to daleko i sve drugo, ostavljajući nas sa samo sedam.

277
00:16:25,150 --> 00:16:30,490
Idemo dati aplauz. Našli smo 7 opet. [Pljesak] Ok. Naravno.

278
00:16:30,490 --> 00:16:32,220
Objesite na samo 1 više drugi.

279
00:16:32,220 --> 00:16:36,630
Iako da sljedeći proces vrsta je malo duže nego što smo osjetili da bi,

280
00:16:36,630 --> 00:16:40,150
Iskreno, vaši prvi instinkti bili najbolji, zar ne? Našli smo 7 trenutno.

281
00:16:40,150 --> 00:16:46,740
No, mi bi našli sedam brže, bez obzira što u ovom primjeru u odnosu na ovaj jedan

282
00:16:46,740 --> 00:16:50,100
jer ako su brojevi sve su razvrstani, baš kao i na stranicama telefonskog imenika,

283
00:16:50,100 --> 00:16:54,580
što doista može usitniti polovicu problema opet i opet i opet.

284
00:16:54,580 --> 00:16:56,740
A to nije baš tako lako vidjeti ovaj sa samo osam brojeva

285
00:16:56,740 --> 00:17:00,100
za razliku od 1000-stranice telefonskog imenika gdje se stvarno ga vide vizualno,

286
00:17:00,100 --> 00:17:03,120
ali u ovom slučaju ovdje kad Sean je u potrazi za sedam,

287
00:17:03,120 --> 00:17:06,020
koliko koraka u najgorem slučaju bi to ga uzeti? >> [Student] 7.

288
00:17:06,020 --> 00:17:11,670
7 u najgorem slučaju. Pa, u najgorem slučaju ne 7 ako ima osam vrata ovdje.

289
00:17:11,670 --> 00:17:13,440
To bi trebalo mu osam koraka.

290
00:17:13,440 --> 00:17:18,170
>> Dakle, ako postoji n vrata, možda su se Sean prije par godina n korake.

291
00:17:18,170 --> 00:17:21,520
Sada, u vašem slučaju, Alex, s obzirom da su ti brojevi sortiraju -

292
00:17:21,520 --> 00:17:25,130
i možemo vrsta zaključiti ovaj odakle smo bili do sada u ovoj priči -

293
00:17:25,130 --> 00:17:28,300
što je trčanje vrijeme Alex je više inteligentnog algoritma

294
00:17:28,300 --> 00:17:30,770
počevši od sredine, a zatim ponavlja?

295
00:17:30,770 --> 00:17:36,490
[Student] 3. >> Dakle, to će biti 3, ugrubo, ako idete 8-4 2 do 1.

296
00:17:36,490 --> 00:17:40,660
Dakle, tri koraka ili, općenito, da je zapisnik n opet.

297
00:17:40,660 --> 00:17:43,380
Svaki put kad si prepoloviti i prepoloviti i prepoloviti i prepoloviti,

298
00:17:43,380 --> 00:17:45,290
to je izraz tog ideje log n.

299
00:17:45,290 --> 00:17:48,140
I tako da bi uzeli vam samo 3 koraka, i doista je to učinio

300
00:17:48,140 --> 00:17:50,890
kada smo otvorili vrata prepoloviti i prepoloviti,

301
00:17:50,890 --> 00:17:53,770
dok bi to uzeti Sean neke 7 ili 8 koraka.

302
00:17:53,770 --> 00:17:56,330
Dakle, hvala vam za bitak s nama ove godine. >> Hvala. Drago mi je da sastanak.

303
00:17:56,330 --> 00:18:00,170
Hvala Alex. >> Isto. [Pljesak]

304
00:18:00,170 --> 00:18:02,150
>> Što je onda stvarna to implicira?

305
00:18:02,150 --> 00:18:06,050
Sada zamislite da to nije osam vrata, koja je, iskreno, svi mi mogli pronaći nešto

306
00:18:06,050 --> 00:18:10,430
iza osam vrata prilično brzo samo po kidanjem komada papira i ide s našim nagonima.

307
00:18:10,430 --> 00:18:14,430
Ali što ako je milijun vrata? Što ako je 4000000000 vrata?

308
00:18:14,430 --> 00:18:19,630
U slučaju 4000000000 vrata, ste stvarno idući u ištanje to ići s Alex je algoritam,

309
00:18:19,630 --> 00:18:23,150
binarno pretraživanje kako ćemo ga početi zovete ili podijeli pa vladaj, općenito,

310
00:18:23,150 --> 00:18:25,220
gdje držite prepolovi i prepolovi problem,

311
00:18:25,220 --> 00:18:30,510
jer ako imate 4000000000 vrata, koliko puta možete usitniti 4000000000 u poluvremenu?

312
00:18:30,510 --> 00:18:33,870
[Student] 32. >> To je zapravo 32. Možete raditi ovo na komad papira ili u vašoj glavi.

313
00:18:33,870 --> 00:18:38,490
Možete ići 4 milijarde do 2 milijarde to 1 milijardu pola milijarde, na 250 milijuna, točka, točka, točka.

314
00:18:38,490 --> 00:18:41,620
A ako ne iz matematike, idete doista dobiti 32,

315
00:18:41,620 --> 00:18:44,950
i da zapravo odnosi na informatici jer smo obično računati u ovlasti dva.

316
00:18:44,950 --> 00:18:47,600
2 do 32 dogoditi da bude 4000000000.

317
00:18:47,600 --> 00:18:51,440
Dakle, postoji puno važnosti za ove vrste moći dva u računalnoj znanosti.

318
00:18:51,440 --> 00:18:55,120
>> Ali što je 8000000000? Koliko koraka je da će se, ako postoje 8000000000 vrata?

319
00:18:55,120 --> 00:19:00,350
[Student] 33. >> Dakle 33. Što ako postoji 16000000000 vrata? Koliko koraka je da će to trajati?

320
00:19:00,350 --> 00:19:05,020
[Student] 34. >> 34. Mogli bismo vrsta nastaviti ovaj nauseam oglasa. No, to je moćna stvar.

321
00:19:05,020 --> 00:19:09,430
Možete uvesti milijarde više ulaza za vaš problem, ali nije velika stvar,

322
00:19:09,430 --> 00:19:14,140
samo uzmete jedan dodatni zalogaj od njega i tako nam daje nešto poput binarnog pretraživanja

323
00:19:14,140 --> 00:19:15,920
ili podijeli pa vladaj, više općenito.

324
00:19:15,920 --> 00:19:17,990
Ali ja sam vrsta varanje ovdje, zar ne?

325
00:19:17,990 --> 00:19:22,410
U slučaju Alex je algoritam, imala je prednost nad Seanom.

326
00:19:22,410 --> 00:19:27,780
Znala je da su ti brojevi su razvrstani, ali Alex nije imala sortirati ih sama.

327
00:19:27,780 --> 00:19:30,520
Ja se unaprijed došao do ploči i vrsti napravio siguran

328
00:19:30,520 --> 00:19:33,670
da sam nacrtao ih sve u sortiraju bi, onda sam ih prekriven papirom.

329
00:19:33,670 --> 00:19:35,850
No, koliko je posla nije da me odvesti?

330
00:19:35,850 --> 00:19:40,110
Ako smo krenuli s tim brojevima u nekom naizgled nasumičnim redoslijedom -

331
00:19:40,110 --> 00:19:43,320
u ovom slučaju te jednostavniji brojevi, jedan kroz osam ovdje -

332
00:19:43,320 --> 00:19:46,090
kako ćemo ići o razvrstavanju tih vrijednosti?

333
00:19:46,090 --> 00:19:52,530
Ako ste bili čovjek dao ovaj zadatak, kakav intuitivan pristup bi vam se

334
00:19:52,530 --> 00:19:54,800
za sortiranje cijela hrpa brojeva?

335
00:19:54,800 --> 00:19:57,050
Ove stvari su postavljeni kao slagalice. Da.

336
00:19:57,050 --> 00:19:59,950
>> [Student] ja bi se svaki broj i usporedi ga svaki

337
00:19:59,950 --> 00:20:03,180
i zadržati ide na lijevo. >> Dobro, dobro.

338
00:20:03,180 --> 00:20:05,720
Tako se svaki broj, usporedite ga jedan pored nje,

339
00:20:05,720 --> 00:20:09,610
i onda samo držati se kreće zajedno s popisom, vrste rejiggering stvari kao i ti ići.

340
00:20:09,610 --> 00:20:13,800
Dakle, ovdje imamo priliku za možda nekoliko više ljudi da se uključe.

341
00:20:13,800 --> 00:20:16,290
Nemojte mi imamo osam više volontera koji bi rado došli do?

342
00:20:16,290 --> 00:20:23,950
Malo manji pritisak jer niste jedini. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Dođite na dolje. Vi ćete biti brojevi 1 do 8.

344
00:20:28,190 --> 00:20:36,050
Idemo vidjeti ako mi to ne može učiniti sortiranje za Alex mnogo na isti način na koji sam to učinio u unaprijed.

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

346
00:20:37,640 --> 00:20:40,760
Idi naprijed i ako bi, redati na pozornici između glazbeni stalak i mene ovdje

347
00:20:40,760 --> 00:20:44,960
u istim redoslijedom kao slajd na zaslonu.

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

349
00:20:50,370 --> 00:20:53,230
Mi ćemo vam raditi u sljedećem primjeru. Oh, čekaj, čekaj. Ovdje ćemo ići. Čekaj.

350
00:20:53,230 --> 00:20:57,570
Sljedeći primjer je sada. Ovdje možete ići. Broj 8. Dođi gore.

351
00:20:57,570 --> 00:21:00,270
U redu. Sortiraj sami prema ovome.

352
00:21:00,270 --> 00:21:03,620
Slide samo malo na strani glazbe stajati ovdje.

353
00:21:03,620 --> 00:21:12,310
Dakle, imamo 4, 2, 6 - doći tamo, ovamo, tamo - tri.

354
00:21:12,310 --> 00:21:17,570
Da. Ok. Možete ići ovamo. Ne, ostani tu.

355
00:21:17,570 --> 00:21:21,840
Da, upravo tamo. Ne, ja sam u krivu. Upravo tamo. Dobro, vrlo dobro. Ok.

356
00:21:21,840 --> 00:21:24,930
Dakle, sada ćemo ih sortirati u rastućem redoslijedu.

357
00:21:24,930 --> 00:21:26,210
>> Kako mogu ići o događaj ovaj?

358
00:21:26,210 --> 00:21:28,630
Algoritam koji je predložio trenutak prije bila zašto ne bismo samo usporediti

359
00:21:28,630 --> 00:21:31,970
su ljudi koji su vrsta jedni pored drugih, a zatim popraviti sve greške,

360
00:21:31,970 --> 00:21:33,540
kreće s lijeva na desno.

361
00:21:33,540 --> 00:21:36,580
Dakle, ovdje imamo četiri i dvije, očito iz reda. Ajmo vas zamijeniti. Ok.

362
00:21:36,580 --> 00:21:40,760
Dakle, sada idem za kretanje prema dolje liniju. 4 i 6, nope. [Smijeh]

363
00:21:40,760 --> 00:21:45,010
6 i 8, prilično dobro. 8 i 1, dopustite mi da vam zamijene dečki. U redu.

364
00:21:45,010 --> 00:21:48,030
Dakle 8 i 3, swap vam dečki.

365
00:21:48,030 --> 00:21:52,280
8 i 7, dopustite mi da vam zamijene dečki. 5 i 8, odličan.

366
00:21:52,280 --> 00:21:54,820
Dajem vam sortirani popis.

367
00:21:54,820 --> 00:21:56,860
U redu. Dakle, ne sasvim.

368
00:21:56,860 --> 00:22:01,180
No, to je bolje, jer su veći brojevi - Slučaj u točki 8 -

369
00:22:01,180 --> 00:22:04,030
su vrsta bubbled se s lijeve na desnu.

370
00:22:04,030 --> 00:22:08,010
Tako sam dobio jedan od njih u pravu, ali to se osjeća kao što je ovaj nije sasvim riješiti problem.

371
00:22:08,010 --> 00:22:11,150
>> Pa što bi ti predlažeš mi učiniti sljedeće? >> [Student] Neka to rade. >> Mi zadržati to.

372
00:22:11,150 --> 00:22:13,740
I shvatili, opet, postavili smo stvari koje samo što sve ljude

373
00:22:13,740 --> 00:22:17,180
vrsta inteligentno se dogovoriti na temelju toj slici,

374
00:22:17,180 --> 00:22:19,040
ali sada moramo biti puno više metodičan.

375
00:22:19,040 --> 00:22:21,510
Moramo biti algoritamski o tome kao da smo pisanje koda -

376
00:22:21,510 --> 00:22:23,520
u ovom slučaju verbalnog pseudocode.

377
00:22:23,520 --> 00:22:26,040
Pa neka mi samo pokušati opet. To je radio prilično dobro. To nije ga riješiti.

378
00:22:26,040 --> 00:22:30,400
No, kada je bez sumnje, samo probati i pokušajte ponovno. Dakle, 2 i 4, nije pomoglo više.

379
00:22:30,400 --> 00:22:33,200
4 i 6. Ah! 6 i 1, malo bolje sada.

380
00:22:33,200 --> 00:22:39,740
6 i 3, dobro. 6 i 7, 7 i 5, 7 i 8, dobro.

381
00:22:39,740 --> 00:22:44,060
A znate, ja vjerojatno ne može ignorirati 8 sada, jer on je na kraju popisa.

382
00:22:44,060 --> 00:22:47,250
Možda mi ne morate brinuti o nekome tko ide pored njega.

383
00:22:47,250 --> 00:22:49,240
Ali neka je vidjeti ako to je sigurno pretpostavka.

384
00:22:49,240 --> 00:22:52,340
Sada je popis - prokleto - nije riješeno. Pokušajmo ovo ponovno.

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

386
00:22:56,440 --> 00:22:59,230
4 i 6, dobro. 6 i 5, dobro.

387
00:22:59,230 --> 00:23:04,890
6, 7, i 8, dobro. No, obavijest, mogu samo zaustaviti ovdje i sada zaustaviti ovdje sada?

388
00:23:04,890 --> 00:23:07,770
[Student] Da. >> Da?

389
00:23:07,770 --> 00:23:11,160
Što ako je netko od vas bio broj 9 skroz tamo?

390
00:23:11,160 --> 00:23:13,640
To bi bio razvrstani. >> Dobro. To bi bio razvrstani prvi put okolo.

391
00:23:13,640 --> 00:23:16,050
Dobar. Dakle idemo opet. Skoro smo tamo.

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

393
00:23:22,800 --> 00:23:26,640
>> Ja sam učinio, ali sada, opet, ja sam računalo koje mogu učiniti samo ono što sam rekao da ne,

394
00:23:26,640 --> 00:23:30,120
i moja jedina uspomena sada je da sam zapravo samo učinio malo rada.

395
00:23:30,120 --> 00:23:31,700
Nešto promijenilo ovdje.

396
00:23:31,700 --> 00:23:37,100
Dakle, nisam tehnički potvrdio vizualno ili algoritamski da ovaj popis je doista riješeno.

397
00:23:37,100 --> 00:23:40,720
Dakle, samo za dobru mjeru, samo da se analni o tome, hajdemo to učiniti jednom više vremena.

398
00:23:40,720 --> 00:23:44,040
Dakle 1 i 2, 2 i 3, 3 i 4. I znate što?

399
00:23:44,040 --> 00:23:46,190
Samo za dobru mjeru, ja ću pratiti na mojoj ruci ovaj put

400
00:23:46,190 --> 00:23:51,110
koliko swaps sam napraviti samo tako da znam koliko posla sam zapravo učinio.

401
00:23:51,110 --> 00:23:56,930
3 i 4, 4 i 5, 5 i 6, 6 i 7, 7 i 8. Nema zamjene.

402
00:23:56,930 --> 00:24:00,800
Dakle, sada sam legitimno biti idiot da to učinite opet

403
00:24:00,800 --> 00:24:03,330
jer ako sam ne raditi kroz ovaj prolaz ljudi,

404
00:24:03,330 --> 00:24:06,710
onda je jasno da će se to opet dogoditi ako nitko od njih je nekako slučajno

405
00:24:06,710 --> 00:24:10,410
adversarially se kreće oko. Dakle, sada mogu prestati.

406
00:24:10,410 --> 00:24:15,120
Sada ćemo postaviti pitanje, koliko posla je to zapravo me odvesti?

407
00:24:15,120 --> 00:24:18,260
Koliko koraka nije to trajati? >> N kvadrat.

408
00:24:18,260 --> 00:24:20,400
Da, tako n kvadratna. Odakle ti n kvadratna iz?

409
00:24:20,400 --> 00:24:22,660
Morate provjeriti svaki NUM -

410
00:24:22,660 --> 00:24:26,530
Tu je n broj, a vi morate provjeriti svaki broj s drugim n brojeva.

411
00:24:26,530 --> 00:24:29,030
Dobar. >> Dakle, to je n kvadratna. >> Dobro.

412
00:24:29,030 --> 00:24:31,060
>> Dakle, ona se osjeća kao da bi mogao vrlo dobro biti n kvadratna, zar ne?

413
00:24:31,060 --> 00:24:33,820
Tu je n od tih momaka, 8 konkretno u ovom slučaju,

414
00:24:33,820 --> 00:24:37,590
ali svaki put kad sam prošao kroz ovaj popis sam uspoređujući prvu osobu protiv drugi,

415
00:24:37,590 --> 00:24:39,650
drugi protiv treći opet i opet i opet,

416
00:24:39,650 --> 00:24:42,450
i kad sam dobio na kraju, što sam učinio? Ja ga redid.

417
00:24:42,450 --> 00:24:46,280
Dakle, ako smo generalizirati ovo objašnjenje, mi smo n ljudima

418
00:24:46,280 --> 00:24:51,090
i sam što, očito, 8 koraka, n koraka, svaki put sam proći kroz ovaj algoritam.

419
00:24:51,090 --> 00:24:56,070
No, koliko puta u najgorem slučaju moram ići kroz ovaj popis ljudi?

420
00:24:56,070 --> 00:24:59,370
[Student] N puta. >> Vjerojatno n, desno, jer u najgorem slučaju,

421
00:24:59,370 --> 00:25:03,410
što je vjerojatno najgori slučaj aranžman od tih dečki iz get-ići?

422
00:25:03,410 --> 00:25:06,520
Ako ste potpuno obrnut poredak

423
00:25:06,520 --> 00:25:09,310
jer samo pretpostavljam psihički, let's - Koje je vaše ime? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Ok. Dakle Bowen, dolaze ovamo samo na trenutak.

425
00:25:12,510 --> 00:25:16,150
>> Pretpostavimo da je Bowen je ovdje na početku algoritma,

426
00:25:16,150 --> 00:25:19,790
i mi ne znamo što svi drugi, ali ovdje Bowen, prema ovom algoritmu -

427
00:25:19,790 --> 00:25:23,820
a ako želite samo šetati sa mnom - ide na balon up, kao što je učinio prvi put oko,

428
00:25:23,820 --> 00:25:25,740
sve do kraja.

429
00:25:25,740 --> 00:25:29,400
Ali pretpostavimo da je osoba pored Bowen je bio broj 7.

430
00:25:29,400 --> 00:25:33,450
Moram se vratiti i dobiti broj sedam, što znači da moram ići sve na putu natrag ovdje.

431
00:25:33,450 --> 00:25:36,980
Sada moram imati taj isti šetnji s osobom koja je broj 7.

432
00:25:36,980 --> 00:25:40,140
No, što ako onda broj 6 je pokraj njega kao dobro?

433
00:25:40,140 --> 00:25:42,180
Onda moram se vratiti i dobiti šest.

434
00:25:42,180 --> 00:25:46,490
Pa opet, na svakoj iteraciji ove petlje govorim da svaki od n ljudi,

435
00:25:46,490 --> 00:25:50,090
i ja morati napraviti n od tih šetnje kako bi bili sigurni ja se povlačim

436
00:25:50,090 --> 00:25:53,760
sve od najvećih elemenata leđa i natrag i natrag na samom kraju popisa.

437
00:25:53,760 --> 00:25:58,230
Dakle, n stvari n puta je samo n puta n ili n kvadratna.

438
00:25:58,230 --> 00:26:02,050
>> Dakle, ovdje već imamo algoritam koji je više ne n, koje više nisu dnevnik n,

439
00:26:02,050 --> 00:26:04,820
to je zapravo gore nego bilo što smo učinili prije.

440
00:26:04,820 --> 00:26:09,840
Dakle, Alex vrsta posrećilo u to sam učinio sve djelo očito up front za nju,

441
00:26:09,840 --> 00:26:14,690
sve skuplji rad, tako da je mogla uživati ​​u ovom binarnom pretraživanje algoritam,

442
00:26:14,690 --> 00:26:16,420
što je log n.

443
00:26:16,420 --> 00:26:18,240
No, to je u skladu s ponedjeljak na temu.

444
00:26:18,240 --> 00:26:23,260
Dali smo malo više prostora, koristili smo više bitova, kako bi se ubrzao naše vrijeme rada.

445
00:26:23,260 --> 00:26:26,170
Toliko se kao da je to trade-off između vremena i prostora,

446
00:26:26,170 --> 00:26:31,060
Također bi mogla biti samo ustupke između vrijeme provedeno do prednjeg vrstu dobivanje stvari spremni otići

447
00:26:31,060 --> 00:26:35,000
i stvarno izvršenje algoritam kao pretraživanja. Pokušajmo još jednom.

448
00:26:35,000 --> 00:26:39,050
Ako vi ne bi smetalo samo brzo preraspodjela sami odgovarati da opet,

449
00:26:39,050 --> 00:26:42,240
ajmo probati nešto malo drugačiji, gdje je ne sasvim kao jednostavan

450
00:26:42,240 --> 00:26:45,760
kao samo popraviti sve pairwise pogreške, što je super intuitivno.

451
00:26:45,760 --> 00:26:48,150
Hajdemo umjesto toga biti malo više namjerno i to.

452
00:26:48,150 --> 00:26:51,010
Ovo je jedna previše bih predložiti je vjerojatno prilično intuitivno.

453
00:26:51,010 --> 00:26:55,070
>> Ajmo odaberite najmanji osobu s popisa i opet. Dakle, ovdje mi ići.

454
00:26:55,070 --> 00:26:57,350
4, vi ste najmanji čovjek sam tako vidio do sada,

455
00:26:57,350 --> 00:27:00,520
tako da ću psihički sjetiti da je samo pokazujući na tebe za sada.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Zaboravite broj četiri. Upravo sam pronašao novi najmanji element u ovom popisu.

457
00:27:05,020 --> 00:27:07,410
Idem vrste sjetiti da. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Doviđenja. Dakle, sada ću se sjetiti broj jedan.

459
00:27:11,190 --> 00:27:14,790
Mi znamo da je jedan je najmanja, ali sam računalo. Što ako postoji 0?

460
00:27:14,790 --> 00:27:17,140
Što ako postoji -1? Moram zadržati ide.

461
00:27:17,140 --> 00:27:20,990
Dakle 3, 7, 5, nope. Ok. Dakle, broj 1 je najmanji.

462
00:27:20,990 --> 00:27:23,640
Dopustite mi da vas odabrati iz popisa - hrapavi ići na ovaj način -

463
00:27:23,640 --> 00:27:27,760
i staviti proizvoljno na početku popisa.

464
00:27:27,760 --> 00:27:29,740
Sada, pričekajte malo. Nekako prevareni.

465
00:27:29,740 --> 00:27:34,010
Ako ti dečki ne predstavljaju popis osam osoba, ali je polje,

466
00:27:34,010 --> 00:27:37,050
8 komada memorijskog - ti smeta povlači za samo trenutak?

467
00:27:37,050 --> 00:27:39,060
Tu je zapravo nema mjesta za vas ovdje.

468
00:27:39,060 --> 00:27:41,840
Pa kako ćemo napraviti prostor za - ono što je vaše ime? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kako ćemo napraviti prostor za Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Mi premjestiti n koji su prije mene. >> Ok.

471
00:27:46,760 --> 00:27:48,850
Tako smo mogli kretati n ljude koji su prije njega,

472
00:27:48,850 --> 00:27:52,400
pa ako vi želite da se jedan namjerno, dramatičan korak s lijeve strane.

473
00:27:52,400 --> 00:27:57,000
Oni sve učinio da u sklad, ali zadnji put sam pisao neki kod,

474
00:27:57,000 --> 00:27:59,740
ne možete sortirati od presele mnoge stvari odjednom.

475
00:27:59,740 --> 00:28:02,450
Mogli smo to učiniti u petlji, kreće sve u jednom trenutku.

476
00:28:02,450 --> 00:28:04,340
Dakle, ako vi ne bi smetalo odstupi s desne strane,

477
00:28:04,340 --> 00:28:07,230
i Sammy, ako bi korak unatrag jer je još uvijek nema mjesta za tebe,

478
00:28:07,230 --> 00:28:11,420
sad ajmo to učiniti. Gdje je Sammy trenutak prije? Upravo tamo.

479
00:28:11,420 --> 00:28:16,140
Dakle, postoji jaz postoji. Dakle, da bi mogao preseliti u Sammy na licu mjesta.

480
00:28:16,140 --> 00:28:20,580
Sada sljedeća osoba i sada sljedeća osoba, sada sljedeća osoba. Sada imamo prostora za Sammy.

481
00:28:20,580 --> 00:28:23,490
Sada, netko iz publike - što je bilo dobro, da je bio ispravan,

482
00:28:23,490 --> 00:28:27,070
osjećala sam se malo vremena - što je brže? Da.

483
00:28:27,070 --> 00:28:29,440
[Student] Novi niz? >> Što je to? >> [Student] Novi niz? >> Dobro, dobro.

484
00:28:29,440 --> 00:28:33,200
>> Dakle, u skladu s ovom temom samo ustupaka, zašto ne bih jednostavno napraviti novi niz

485
00:28:33,200 --> 00:28:36,570
 i onda Sammy će se kupati u prostoru ispred tih ljudi, na primjer,

486
00:28:36,570 --> 00:28:39,600
a mi samo možemo početi punjenje novi niz uopce. To je previše raditi.

487
00:28:39,600 --> 00:28:42,450
Ali ja nisam zainteresiran za trošenje više prostora danas. Što je drugi pristup?

488
00:28:42,450 --> 00:28:46,630
[Student] Zamijeni. >> Ok. Mi smo samo mogli zamijeniti ove dvije dečki. Koje je vaše ime?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Dakle, Mario, bili ste trenutno ovdje.

490
00:28:49,390 --> 00:28:52,480
Sammy, možete backup samo na trenutak? Mario je bio ovdje.

491
00:28:52,480 --> 00:28:55,830
Nemamo prostora za vas više, pa ako ne bi smetalo ide gdje Sammy je,

492
00:28:55,830 --> 00:29:02,430
ćemo staviti Sammy ovdje, i sada bih tvrditi da je Sammy zamjene operacija bila mnogo brže.

493
00:29:02,430 --> 00:29:06,370
Napravili smo jedan rad zamijeniti ove momke, ili možda dvije da zamijene ove momke,

494
00:29:06,370 --> 00:29:11,210
ali nismo to 1, 2, 3, 4, tako da se osjeća bolje. Sada, pričekajte malo.

495
00:29:11,210 --> 00:29:14,660
Nekako mi je problem pogoršava, jer broj 4 je nekako blizu početka.

496
00:29:14,660 --> 00:29:19,470
Sada broj 4 je malo bliže tom cilju, ali ja ne znam ili briga o tome.

497
00:29:19,470 --> 00:29:23,330
Dakle, ovo je samo loša sreća da je broj četiri je malo dalje od svoje predodređen mjesto.

498
00:29:23,330 --> 00:29:25,110
Dakle, ajmo sad ponoviti ovaj algoritam.

499
00:29:25,110 --> 00:29:28,410
>> Da podsjetimo, dokle god ta priča bila, sve mi je bilo hodati po popisu

500
00:29:28,410 --> 00:29:31,130
u potrazi za najmanjim brojem osoba.

501
00:29:31,130 --> 00:29:34,530
Pa sada neka to učiniti opet. Mi ne moramo brinuti o Sammy više.

502
00:29:34,530 --> 00:29:37,590
Možemo samo ići ovdje. Ooh! Broj 2. To je prilično mali broj.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Dobro, dobro.

504
00:29:41,180 --> 00:29:43,770
I srećom, slučajno, ne moram da se presele - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie, jer on je u svom pravom mjestu sada.

506
00:29:45,910 --> 00:29:48,110
Ajmo to učiniti opet i ignorirati ove dvije dečki.

507
00:29:48,110 --> 00:29:50,460
6. To je prilično mali broj. Ooh! 8 je definitivno veća.

508
00:29:50,460 --> 00:29:53,410
4. Neka se usredotočiti na četiri. Ooh! 3 je čak i bolje.

509
00:29:53,410 --> 00:29:58,290
7 i 5. Pa što ćemo učiniti sada s - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Idemo ga zamijeniti s brojem šest.

511
00:30:00,250 --> 00:30:03,570
Dakle, ako šest i tri željeli mijenjati,

512
00:30:03,570 --> 00:30:07,320
sada smo vrsta stečen sretan u tom 6 je bliže, gdje bi trebala biti,

513
00:30:07,320 --> 00:30:10,300
ali to je samo slučajnost ovdje. Dakle, ajmo sad ići tamo.

514
00:30:10,300 --> 00:30:13,430
8 je prilično mali broj. Ooh! 4 je manji.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Što ćemo sad učiniti? >> Zamijeni. >> Točno.

516
00:30:17,130 --> 00:30:19,010
Dakle, sada idemo napraviti ovu vrstu brže.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Odakle 5 ići? Dobar. Ok.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 dobiva ostati gdje je. Koje je vaše ime? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie dobiva ostati gdje je. 7 dobiva - Idemo vidjeti. 7, 8. Ok.

520
00:30:31,770 --> 00:30:35,100
Dakle, sedam dobiva ostati gdje je. Koje je vaše ime? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Dakle, Amna dobiva ostati gdje je, a broj 8 je već gdje on sada treba biti.

522
00:30:39,670 --> 00:30:43,960
Dobro, dobro. Osjeća se kao da smo tek stvara posao za sebe ovdje, ipak.

523
00:30:43,960 --> 00:30:47,440
Što je u konačnici trajanje tog algoritma?

524
00:30:47,440 --> 00:30:51,900
Ako mislimo o tim ljudima ne kao 8 ali kao n? >> To je n.

525
00:30:51,900 --> 00:30:55,440
To je n koraka, ali mi provjeravamo svaki put.

526
00:30:55,440 --> 00:30:57,570
Ok. N, ali ti si provjeri svaki put?

527
00:30:57,570 --> 00:31:03,450
Ok, ali ako to n koraka, ne bih bio u mogućnosti da vam sortirati samo ide 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Ok, to je velika razlika.

529
00:31:05,590 --> 00:31:08,050
Dakle, n četvrtasti zašto? Što se zapravo događa?

530
00:31:08,050 --> 00:31:12,130
Tu je n ljudi u ovom popisu, ali da se naći najmanji osobu na popisu

531
00:31:12,130 --> 00:31:16,200
u najgorem slučaju, koliko koraka moram uzeti? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, pravo, jer u najgorem slučaju, broj jedan je skroz tamo,

533
00:31:19,160 --> 00:31:20,990
tako da moram ići ga ili nju.

534
00:31:20,990 --> 00:31:25,500
I onda kad sam napokon shvate 1 je najmanji, onda je prilično brzo kako bi ih zamijeniti.

535
00:31:25,500 --> 00:31:28,450
Ali sada moram početi od početka i tražiti tko?

536
00:31:28,450 --> 00:31:31,980
Sljedeći najmanji osoba, što je 2. Gdje u najgorem slučaju je 2?

537
00:31:31,980 --> 00:31:34,320
Oh, moj Bože. To je sve način ovdje na kraju.

538
00:31:34,320 --> 00:31:37,000
Dakle, sada sam upravo učinio još n koraka, još n koraka.

539
00:31:37,000 --> 00:31:41,200
I ako imamo n ljude iu najgorem slučaju najmanji čovjek je n koraka,

540
00:31:41,200 --> 00:31:45,230
to je opet n puta n, pa smo opet n kvadratna.

541
00:31:45,230 --> 00:31:47,280
To se ne osjeća tako dobro.

542
00:31:47,280 --> 00:31:52,150
A u stvari, čak iu najboljem slučaju - Pretpostavljam da počnete razvrstani -

543
00:31:52,150 --> 00:31:59,080
koliko koraka je potrebno za mene koristeći ovaj algoritam za sortiranje tih n ljude?

544
00:31:59,080 --> 00:32:01,010
N kvadrat. >> Čuo sam n kvadratna. Zašto n kvadrat?

545
00:32:01,010 --> 00:32:05,240
Budući da još uvijek imate da provjerite svaki put. >> Da.

546
00:32:05,240 --> 00:32:08,060
I imate kako bi ih zamijeniti. >> Iako mi ljudi su vrsta sveznajući

547
00:32:08,060 --> 00:32:10,770
u smislu vizualno da možemo samo vrsta vidjeti da je to razvrstani,

548
00:32:10,770 --> 00:32:12,140
računalo nije toliko pametan.

549
00:32:12,140 --> 00:32:14,040
To će se pogledati ovdje i ovdje i ovdje,

550
00:32:14,040 --> 00:32:16,610
ali ako je ono što se traži je najmanji element,

551
00:32:16,610 --> 00:32:22,110
vi samo znate da ste pronašli najmanji element po tome što reći? Nakon što ste na kraju.

552
00:32:22,110 --> 00:32:25,880
No, u tom trenutku, da ste samo našli trenutno najmanji element.

553
00:32:25,880 --> 00:32:28,810
Vi ne nužno znati ništa drugo o stanju u svijetu.

554
00:32:28,810 --> 00:32:30,880
Dakle, morate ići opet i opet i opet.

555
00:32:30,880 --> 00:32:34,880
>> Dakle, ovaj put sam stvarno izgleda glupo jer sam provjeru, ok, dvije, ti si najmanji,

556
00:32:34,880 --> 00:32:37,530
ali ne znam da je u ukupno gostiju.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Dobro, dobro. 2 je doista najmanji.

558
00:32:41,090 --> 00:32:43,150
Sada ćemo pronaći sljedeći najmanji. Ok.

559
00:32:43,150 --> 00:32:48,350
3, ti si trenutno najmanji. Idemo vidjeti. 4, 5, 6, 7, 8. Ok, posrećilo opet.

560
00:32:48,350 --> 00:32:53,170
3 je doista na pravom mjestu. Ali ja ću zadržati to opet i opet i opet.

561
00:32:53,170 --> 00:32:55,990
Kako možemo učiniti ikada tako nešto bolje?

562
00:32:55,990 --> 00:33:00,120
Umjesto da ljudi balon se pojava udvojenih od najmanjih do najvećih

563
00:33:00,120 --> 00:33:04,350
i umjesto da ide natrag i naprijed kroz popisu se odabire onda najmanji osobu,

564
00:33:04,350 --> 00:33:09,780
zašto ne bismo umjesto umetnuti te ljude u novi popis korak po korak?

565
00:33:09,780 --> 00:33:13,080
Pokušajmo ovo. Sada me zovu ovu vrstu stvar umetanja.

566
00:33:13,080 --> 00:33:17,250
Dakle, ovdje smo ovdje. Broj jedan. Ja ne brinuti se o bilo tko drugi u ovom popisu.

567
00:33:17,250 --> 00:33:21,310
Moj cilj sada je pravo staviti broj jedan na početku sortirane liste.

568
00:33:21,310 --> 00:33:23,910
I ja ću predložiti jer imam samo 8 komade memorije,

569
00:33:23,910 --> 00:33:28,670
samovoljno upravo sada sam zid između moje navodno nerazvrstani popisu,

570
00:33:28,670 --> 00:33:32,740
i svatko tko je iza mene ću tvrditi je riješeno.

571
00:33:32,740 --> 00:33:34,680
Tako sada imamo broj jedan.

572
00:33:34,680 --> 00:33:39,240
Želim ga umetnuti u mom sortirani popisu, tako da sam samo ću premjestiti moj zid ovamo,

573
00:33:39,240 --> 00:33:43,930
i sada tvrdim ovaj popis sortira, ovaj popis je nesortirani - barem koliko ja znam.

574
00:33:43,930 --> 00:33:46,070
Ja ne mogu vidjeti sve brojeve odjednom.

575
00:33:46,070 --> 00:33:49,000
>> Sada sam se dogoditi da naiđete broj dva. Što da radim s njim?

576
00:33:49,000 --> 00:33:54,380
Ja vam umetnuti sada u sortirani popis. Ali primijetite kako je lako.

577
00:33:54,380 --> 00:33:59,650
Imam samo gledati. Broj jedan je tamo. Oh, očito dva odlazi na strani broj 1.

578
00:33:59,650 --> 00:34:03,700
Sada što da radim sa 3? Ja vas umetnuti u sortirani popis. Ali to je bilo super jednostavno.

579
00:34:03,700 --> 00:34:07,250
Ovo je super jednostavno, ovo je super jednostavno, ovo je super jednostavno, super jednostavno, super jednostavno.

580
00:34:07,250 --> 00:34:12,790
I sada je sve razvrstani iza mene, i koliko koraka nije to trajati?

581
00:34:12,790 --> 00:34:15,620
[Studenti] N. >> Dakle, to je samo n. Imali smo sreće.

582
00:34:15,620 --> 00:34:18,860
To je bio samo n zašto? >> [Student] Zato je popis sortiran.

583
00:34:18,860 --> 00:34:21,630
Popis je već riješeno. Dakle, mi se posrećilo.

584
00:34:21,630 --> 00:34:25,639
Ali smo osmislili algoritam ovaj put da harnesses takvu sreću,

585
00:34:25,639 --> 00:34:29,420
koji najbolje scenarij, a ne gubit vrijeme nepotrebno.

586
00:34:29,420 --> 00:34:31,750
Tako sada imamo ono što ćemo nazvati balon vrste

587
00:34:31,750 --> 00:34:33,949
gdje su ljudi vrsta balona do pairwise.

588
00:34:33,949 --> 00:34:38,100
Mi sada imamo izbor vrsta gdje smo iščupati najmanji osobu iznova i iznova.

589
00:34:38,100 --> 00:34:42,350
I sada imamo unosa vrsta gdje smo vrsta proaktivno staviti ljude kojima oni pripadaju

590
00:34:42,350 --> 00:34:45,000
u sve sortirane liste.

591
00:34:45,000 --> 00:34:49,679
Ako smo mogli, aplauz za ove dečke ovdje. [Pljesak]

592
00:34:49,679 --> 00:34:52,310
Uzmimo naš 5-minutni predah ovdje.

593
00:34:52,310 --> 00:34:55,139
A kad smo se vratiti, mi ćemo odsvirati svih tih algoritama iz vode

594
00:34:55,139 --> 00:35:00,260
s nečim boljim. U redu. Hvala vam puno. Možete zadržati one kao suvenire.

595
00:35:01,710 --> 00:35:04,330
U redu. Mi smo natrag.

596
00:35:04,330 --> 00:35:08,420
>> I da podsjetimo jako brzo, imali smo ove tri različite pristupe sortiranje,

597
00:35:08,420 --> 00:35:13,000
cijela točka koja je bila doći do točke gdje netko poput Alexa

598
00:35:13,000 --> 00:35:16,930
mogao tražiti popis brojeva brže nego nekoga poput Seana mogao.

599
00:35:16,930 --> 00:35:19,830
I iako imamo takve jednostavne primjere s osam brojeva,

600
00:35:19,830 --> 00:35:24,000
mogli izvesti lako do 8 web stranica, 8000000000 web stranicama,

601
00:35:24,000 --> 00:35:26,680
ili 800 milijuna prijatelja na Facebooku.

602
00:35:26,680 --> 00:35:30,090
Dakle, ovi algoritmi svakako može skalirati na one vrste vrijednosti,

603
00:35:30,090 --> 00:35:32,300
i ideje su u konačnici isti.

604
00:35:32,300 --> 00:35:36,140
Dakle, balon vrsta je bila prva gdje smo vrsta bubbled do najveće osobu

605
00:35:36,140 --> 00:35:39,110
skroz desno zamjene ljude pojava udvojenih.

606
00:35:39,110 --> 00:35:42,040
Tada smo imali ono što ćemo nazvati odabira vrste gdje sam malo više namjerno

607
00:35:42,040 --> 00:35:46,480
zadržao gledajući kroz popis, odabirom najmanji broj opet i opet i opet,

608
00:35:46,480 --> 00:35:49,530
logična posljedica kojih je da je popis na kraju je riješeno.

609
00:35:49,530 --> 00:35:53,780
Onda je u trećem jednom, ja umetnuta ljude u njihovom odgovarajućem mjestu,

610
00:35:53,780 --> 00:35:57,720
i nismo jako neprirodan primjer, da je popis već sortiran,

611
00:35:57,720 --> 00:36:01,100
ali to je bilo poslati poruku da se u Insertion Poredaj slučaju,

612
00:36:01,100 --> 00:36:02,670
možete dobiti sretan.

613
00:36:02,670 --> 00:36:07,930
Ako su brojevi već su razvrstani, samo će vas odvesti n korake kako bi potvrdili koliko,

614
00:36:07,930 --> 00:36:10,870
dok odabira vrste si malo više tunel vizija

615
00:36:10,870 --> 00:36:14,360
i da nikada ne shvate da je popis već riješeno.

616
00:36:14,360 --> 00:36:16,830
Tako ćemo vidjeti mjehurić vrsta u akciji ovdje.

617
00:36:16,830 --> 00:36:19,590
U sljedećem primjeru, mi smo o tome vidjeti okomite pruge

618
00:36:19,590 --> 00:36:23,030
čije visine predstavljaju brojeve, tako da možemo izdvojiti od zamišljati sortiranje dogoditi.

619
00:36:23,030 --> 00:36:26,630
Manji bar, manji broj, to je veći bar, veći broj.

620
00:36:26,630 --> 00:36:28,860
>> A mi ćemo ga igrati na tu zadanu brzinu.

621
00:36:28,860 --> 00:36:33,460
To se događa da se presele malo brzo, za sada, ali crveno je ono što se pokazuje dva bara

622
00:36:33,460 --> 00:36:35,480
se u usporedbi rame uz rame.

623
00:36:35,480 --> 00:36:39,520
A ako ste gledati usko, što se događa je da ako se barovi su od reda,

624
00:36:39,520 --> 00:36:42,300
manji jedan dobiva preselio na lijevo, veću jednog s desne strane,

625
00:36:42,300 --> 00:36:44,360
i onda držati napreduje.

626
00:36:44,360 --> 00:36:48,520
Dakle, ako smo to učiniti opet i opet, primijetiti da najmanji barovi

627
00:36:48,520 --> 00:36:51,090
će zadržati skroz svoj put do lijeve

628
00:36:51,090 --> 00:36:54,130
i najveći barovi će zadržati skroz svoj put na desnoj strani.

629
00:36:54,130 --> 00:36:58,490
I doista, mi smo početkom vidjeti uzorak skroz na desnoj strani

630
00:36:58,490 --> 00:37:04,790
baš kao što smo vidjeli 8 i onda na kraju sedam bubbling do samom kraju našeg ljudskog liste.

631
00:37:04,790 --> 00:37:08,750
Dakle, to će se vrlo brzo dobiti malo zamorno, pa neka me zaustavi na trenutak.

632
00:37:08,750 --> 00:37:10,980
Dopustite mi da promijenite brzinu da će biti puno brži.

633
00:37:10,980 --> 00:37:15,380
Ja ne mijenja algoritam, ja sam samo izradu animacija dogoditi brže.

634
00:37:15,380 --> 00:37:18,410
Ipak bubble sorta, isti algoritam,

635
00:37:18,410 --> 00:37:21,910
ali sada možete vidjeti mnogo brže nego naše verbalne demonstracije

636
00:37:21,910 --> 00:37:25,900
da je najveći elementi uistinu bubbling do vrha.

637
00:37:25,900 --> 00:37:29,860
>> Kao na stranu, ovi mali trgovi na dnu lijevo i dolje desno

638
00:37:29,860 --> 00:37:33,520
samo su mali podsjetnici što bi koliko usporedbe radite.

639
00:37:33,520 --> 00:37:37,620
Ali za sada, možemo se fokusirati na piramidi da je uzimanje oblik, i tamo to ide.

640
00:37:37,620 --> 00:37:41,510
Najmanji element koji je na lijevoj strani, najvećem na desnoj strani, a sve ostalo između.

641
00:37:41,510 --> 00:37:44,470
Sada ćemo umjesto pogledati odabira vrste.

642
00:37:44,470 --> 00:37:47,260
Ja ću ići naprijed i udario Stop. Mi ćemo dobiti novi slučajni niz barova.

643
00:37:47,260 --> 00:37:50,930
Izbor vrsta, podsjetimo, ide kroz popis opet i opet i opet,

644
00:37:50,930 --> 00:37:54,900
čupanje najmanji element. Dakle, ovdje je izbor vrsta.

645
00:37:54,900 --> 00:37:58,390
To izgleda kao da je manje posla događa sada, jer nismo uspoređujući pairwise

646
00:37:58,390 --> 00:38:02,590
ali mi smo samo sortirati od višnje branje najmanji elemente s desna na lijevo.

647
00:38:02,590 --> 00:38:06,890
To je vrlo malo vremena, tako da je dihotomija već.

648
00:38:06,890 --> 00:38:11,820
Samo zato algoritam je rekao da se n kvadratna vremena, kao mjehurić vrste

649
00:38:11,820 --> 00:38:16,100
i kao što je izbor vrste, one su stvarno najgorem slučaju trčanje puta.

650
00:38:16,100 --> 00:38:21,790
Na primjer, u slučaju, recimo, odabir vrsta,

651
00:38:21,790 --> 00:38:27,240
Ja sam zapravo odabirom najmanji osobu i stavljajući ga ili nju ovdje,

652
00:38:27,240 --> 00:38:29,620
onda ću to opet, onda ću to opet,

653
00:38:29,620 --> 00:38:32,070
ali tu je bio blagi optimizacija sam mogao napraviti.

654
00:38:32,070 --> 00:38:35,040
>> Čim sam se preselio broj jedan ovdje - Sammy u tom slučaju -

655
00:38:35,040 --> 00:38:38,630
ono što sam trebate učiniti s njim nakon toga? >> [Student] Ostavite ga.

656
00:38:38,630 --> 00:38:40,140
Pustite ga, zar ne? Ništa.

657
00:38:40,140 --> 00:38:44,310
Nisam trebate ikada razgovarati Sammy ponovno jer ako sam odabrao najmanji element

658
00:38:44,310 --> 00:38:48,580
i staviti ga ovdje, zašto gubiti vrijeme ide do kraja cijeli moj popis?

659
00:38:48,580 --> 00:38:54,590
Na sljedećoj iteraciji neka mi zapravo kretati samo na broj 2, samo na broju tri.

660
00:38:54,590 --> 00:38:57,640
Dakle, u stvarnosti, nisam radila n stvari n puta.

661
00:38:57,640 --> 00:39:05,380
Radim n stvari, onda n - 1 stvari, onda n - 2 stvari, onda n - 3 stvari,

662
00:39:05,380 --> 00:39:07,080
zatim n - 4, točka, točka, točka.

663
00:39:07,080 --> 00:39:09,470
Imamo malo geometrijskog niza, što samo znači

664
00:39:09,470 --> 00:39:11,450
ste zbrajanjem progresivno manje brojeve.

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

666
00:39:17,940 --> 00:39:21,380
A što da uglavnom radi se da se -

667
00:39:21,380 --> 00:39:24,280
Idem nered gore moj brodu ovdje samo na trenutak -

668
00:39:24,280 --> 00:39:28,990
koji će raditi da se nešto poput n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
ako smo samo vrsta izgled na leđima matematike knjige, gdje imate sve Šalabahteri

670
00:39:31,930 --> 00:39:33,410
za formule.

671
00:39:33,410 --> 00:39:37,760
Ako ste samo dodao nešto n + n - 1 + n - 2, to radi da se nešto ovako.

672
00:39:37,760 --> 00:39:42,320
A ako mi samo vrsta pomnožite ovo, da je n kvadrat minus n / 2.

673
00:39:42,320 --> 00:39:46,400
Ja stalno ponavljala n kvadratna, ipak, i to je zato što sam bio vrsta uzimanje mentalni prečac

674
00:39:46,400 --> 00:39:51,950
jer u stvarnosti, n kvadrat minus n dijeli dva je doista istina broj koraka

675
00:39:51,950 --> 00:39:55,510
da algoritam poput odabira vrste bi se, ako mi stvarno broje do

676
00:39:55,510 --> 00:39:58,800
sve te usporedbe i sve malo zauzet radom smo radili.

677
00:39:58,800 --> 00:40:03,210
Ali iskreno, jednom n dobiva se kao milijun ili milijardu, koji je pakao brine

678
00:40:03,210 --> 00:40:07,160
ako radite milijarde kvadratnih minus milijardu podijeljenih po dva?

679
00:40:07,160 --> 00:40:09,320
Milijardi kvadratna je ogroman broj.

680
00:40:09,320 --> 00:40:13,580
Možete uzeti drugi milijardi izvan nje s - n. To nije tako velika stvar.

681
00:40:13,580 --> 00:40:18,770
Dakle, veći su brojevi dobili, manje važni ove niže naredio uvjeti.

682
00:40:18,770 --> 00:40:24,230
Koga briga ako podijelite dva ako govorimo o quadrillions prema broju koraka?

683
00:40:24,230 --> 00:40:29,710
>> Dakle, u cjelini, računalni znanstvenici imaju tendenciju da bacaju sve, ali najveći termin,

684
00:40:29,710 --> 00:40:33,140
a mi samo vrsta pojednostaviti svijet i reći da je algoritam

685
00:40:33,140 --> 00:40:38,130
uzeo otprilike n kvadratna korake. To je trčanje vrijeme algoritma.

686
00:40:38,130 --> 00:40:40,760
Dakle, vratit ćemo se na to samo trenutak s nekim konkretnim primjerima,

687
00:40:40,760 --> 00:40:45,940
ali za sada, to je vrsta intuitivnog motivacije iza samo pojednostavljivanja naš svijet

688
00:40:45,940 --> 00:40:51,170
i govori o najvažnijim terminima nego uzimajući u svim tim fantazija formulama.

689
00:40:51,170 --> 00:40:53,540
Tako da je izbor vrsta, a dobili smo malo sreće tamo.

690
00:40:53,540 --> 00:40:57,360
Pogledajmo unosa vrste. Dopustite mi ići naprijed i početi ovaj jedan kao dobro.

691
00:40:57,360 --> 00:41:00,330
Sada primijetite uzorak koji se događa je malo drugačiji,

692
00:41:00,330 --> 00:41:03,410
i počeli smo sa slučajnim brojevima,

693
00:41:03,410 --> 00:41:06,890
ali ako mi zapravo brojati do broja koraka u najgorem slučaju,

694
00:41:06,890 --> 00:41:11,070
ako je popis započeo potpuno u pravom redoslijedu,

695
00:41:11,070 --> 00:41:13,380
možemo samo bi n korake kako bi shvatili koliko.

696
00:41:13,380 --> 00:41:18,240
>> Ali ako popis su zapravo unatrag - na primjer, u ovom slučaju ovdje -

697
00:41:18,240 --> 00:41:23,860
onda primijetite da zapravo morati učiniti puno više posla u ovom slučaju.

698
00:41:23,860 --> 00:41:27,080
I to bi trebalo nekako osjećam da vam se sviđa ova je vrsta radnog teže

699
00:41:27,080 --> 00:41:30,900
da se one manje elemente s lijeve strane, a to je zato što smo nesretni.

700
00:41:30,900 --> 00:41:34,210
Popis je sortiran slučajno u obrnutom smjeru.

701
00:41:34,210 --> 00:41:38,110
Nasuprot tome, s ugradnjom vrste ako mi oponašaju ono što smo učinili s našim ljudima ovdje

702
00:41:38,110 --> 00:41:42,670
počevši sa svima poredani i onda početi, to je prilično dobar algoritam, zar ne?

703
00:41:42,670 --> 00:41:45,010
To je već, u stvari, razvrstani.

704
00:41:45,010 --> 00:41:48,670
Tako ćemo pokušati sažeti točno koliko vremena te stvari uzimaju nam

705
00:41:48,670 --> 00:41:52,360
uvođenjem samo malo žargon ili zapis koji je zapravo puno jednostavnije

706
00:41:52,360 --> 00:41:54,320
od fanciness vrsta sugerira.

707
00:41:54,320 --> 00:41:59,030
To je stvar ovdje, ovaj veliki O na ekranu, što je računalni znanstvenik uglavnom će koristiti

708
00:41:59,030 --> 00:42:03,640
opisati najgorem slučaju trčanje vrijeme algoritma.

709
00:42:03,640 --> 00:42:07,360
>> Opet, po najgorem slučaju, to je potpuno ovisna o kontekstu.

710
00:42:07,360 --> 00:42:10,890
Što mi znači najgorem slučaju potpuno varira ovisno o problemu govorimo o tome.

711
00:42:10,890 --> 00:42:14,550
No, u slučaju razvrstavanja, što je najgori mogući scenarij?

712
00:42:14,550 --> 00:42:17,860
Sve je unatrag, jer to samo osjeća kao da znači puno posla za nas.

713
00:42:17,860 --> 00:42:21,330
Ja sam zapisao nekoliko algoritama koji smo vidjeli do sada:

714
00:42:21,330 --> 00:42:24,930
linearno pretraživanje, binarno pretraživanje kao s telefonskom imeniku ili komadića papira,

715
00:42:24,930 --> 00:42:28,960
zatim balon vrsta, izbor vrsta i umetanje vrsta kao što smo vidjeli s našim ljudima,

716
00:42:28,960 --> 00:42:31,770
i onda jedan drugi koji je na kraju će biti pozvani spojiti vrsta.

717
00:42:31,770 --> 00:42:37,710
Dakle, u linearnom potrage u najgorem slučaju, koliko koraka je potrebno pronaći broj 7

718
00:42:37,710 --> 00:42:40,690
ako postoji n vrata poput Seana suočeni? >> [Student] N.

719
00:42:40,690 --> 00:42:44,180
N. Tako ćemo pisati veliki O od n.

720
00:42:44,180 --> 00:42:47,010
Samo ću ispuniti u nekim praznine. Ovo je samo mreža praznine.

721
00:42:47,010 --> 00:42:52,990
No, u najboljem slučaju s linearnim pretraživanje, 7 možda su na samom početku popisa,

722
00:42:52,990 --> 00:42:55,520
i Sean možda su počeli u potrazi na početku popisa.

723
00:42:55,520 --> 00:42:58,940
Dakle, ako ste koristeći linearnu pretraživanje i samo provjeri s lijeva na desno ili možda s desna na lijevo -

724
00:42:58,940 --> 00:43:02,650
oni su ekvivalent - u najboljem slučaju koliko koraka možda linearno pretraživanje,

725
00:43:02,650 --> 00:43:05,550
kao Sean algoritma, poduzeti? Samo jedan korak.

726
00:43:05,550 --> 00:43:09,450
>> Dakle, ja ću reći da je omega zapis.

727
00:43:09,450 --> 00:43:11,570
Ovo je samo kapital omega.

728
00:43:11,570 --> 00:43:15,000
Omega je samo seksi način govoreći najboljem slučaju prikazivati ​​vrijeme.

729
00:43:15,000 --> 00:43:18,900
Dakle, u najboljem slučaju, trajanje je jedan korak ili konstantna broj koraka -

730
00:43:18,900 --> 00:43:24,270
1 u ovom slučaju - ali u najgorem slučaju, veliki O, to je zapravo n koraka.

731
00:43:24,270 --> 00:43:28,110
A ovaj ovdje, theta, mi zapravo ne ide pogledati upravo sada.

732
00:43:28,110 --> 00:43:30,090
To nije relevantno za ovaj primjer.

733
00:43:30,090 --> 00:43:31,990
Ali sada pokušajmo binarnog pretraživanja.

734
00:43:31,990 --> 00:43:35,990
U najgorem slučaju s binarnom potrazi, koliko koraka se to događa da se pronaći broj 7

735
00:43:35,990 --> 00:43:38,340
ili što god smo u potrazi za? >> [Student] Prijava n.

736
00:43:38,340 --> 00:43:40,980
Ipak ću uzeti log n, jer baš kao i Alex dobio nesretni

737
00:43:40,980 --> 00:43:44,030
kad smo stvarno radili kroz problem metodički

738
00:43:44,030 --> 00:43:48,220
a ona nije našao broj 7 do posljednjeg vrata Gledala,

739
00:43:48,220 --> 00:43:51,720
iako, u pravednosti, ona je dobio baciti određene vrata na putu,

740
00:43:51,720 --> 00:43:56,920
binarno pretraživanje u najgorem slučaju ima trajanje od log n.

741
00:43:56,920 --> 00:43:59,230
I opet, da govori ova dijeljenjem i osvaja.

742
00:43:59,230 --> 00:44:01,140
Ali što u najboljem slučaju?

743
00:44:01,140 --> 00:44:04,790
A Alex je zapravo doživio taj najboljem slučaju u pravu kada je došla na pozornicu.

744
00:44:04,790 --> 00:44:07,290
Koliko koraka je da se u binarnom potrazi? >> [Student] 1.

745
00:44:07,290 --> 00:44:09,380
1, samo zato što se posrećilo.

746
00:44:09,380 --> 00:44:12,520
Ali to je u redu, jer omega odnosi na najboljem slučaju scenarija,

747
00:44:12,520 --> 00:44:15,770
najboljem slučaju ulaza, čak i ako je samo slučajna glupi sreće.

748
00:44:15,770 --> 00:44:18,900
>> Sada, ovo je previše idemo samo vrsta ostavite prazno za sada.

749
00:44:18,900 --> 00:44:21,010
Kako je sada mjehurić vrsta?

750
00:44:21,010 --> 00:44:24,290
U najgorem slučaju s bubble sort, svatko je u obrnutom redoslijedu,

751
00:44:24,290 --> 00:44:26,380
tako da moramo učiniti puno mjehurića.

752
00:44:26,380 --> 00:44:30,190
No, koliko koraka je da će se u najgorem slučaju? >> [Student] N kvadrat.

753
00:44:30,190 --> 00:44:32,550
To je bio n na kvadrat, jer ako mislite o tome,

754
00:44:32,550 --> 00:44:36,410
ako je popis u potpunosti unatrag - 8 je ovdje, jedan je ovdje -

755
00:44:36,410 --> 00:44:40,530
kao stvar početi mjehur, broj 8 je idući u premjestiti na ovaj način, ovaj put,

756
00:44:40,530 --> 00:44:44,540
na taj način, na taj način, ali gdje je broj 7 u najgorem slučaju?

757
00:44:44,540 --> 00:44:47,720
Ovdje je još uvijek tamo. Dakle, moramo to učiniti opet i opet.

758
00:44:47,720 --> 00:44:53,190
A to je gdje smo dobili n koraka, a zatim n - 1 koraka, a zatim n - 2 koraka.

759
00:44:53,190 --> 00:44:55,960
A ako se uzme moju riječ za to - da, ako vrsta umnožiti se,

760
00:44:55,960 --> 00:45:00,110
to grubo je n kvadrat na kraju s nekim drugim uvjetima koje ćemo samo ignorirati za sada -

761
00:45:00,110 --> 00:45:06,890
onda u najgorem slučaju mjehurića kakve je n kvadratna, dati ili uzeti.

762
00:45:06,890 --> 00:45:09,490
No, što o najboljem slučaju s mjehurićima vrste?

763
00:45:09,490 --> 00:45:13,050
Koji je najbolji mogući scenarij? Sve od brojeva su razvrstani već.

764
00:45:13,050 --> 00:45:15,920
A što je heuristička sam koristio, trik sam koristio,

765
00:45:15,920 --> 00:45:20,110
shvatiti da sam učinio nikakav posao te bi stoga mogla zaustaviti rano?

766
00:45:20,110 --> 00:45:23,590
[Student] Ček jednom. >> Ga Provjerite jednom. No, ono što je sam događaj na putu?

767
00:45:23,590 --> 00:45:26,130
Bio sam praćenje koliko swaps sam napravio.

768
00:45:26,130 --> 00:45:30,650
I shvatio sam da nisam broje nikakve zamjene na prstima, onda sam učinio nikakav posao.

769
00:45:30,650 --> 00:45:34,300
Ja sigurno ne bi trebali pokušati raditi nikakva posla opet, tako da sam samo mogu zaustaviti.

770
00:45:34,300 --> 00:45:37,830
>> Dakle, u najboljem slučaju bubble vrste kada je popis već sortiran,

771
00:45:37,830 --> 00:45:41,530
što će vam reći Omega zapis, najbolji slučaj prikazivati ​​vrijeme?

772
00:45:41,530 --> 00:45:48,040
To je samo n. Moramo napraviti neki posao, ali imamo samo učiniti jedan šetati vrijedi rada.

773
00:45:48,040 --> 00:45:50,490
I ovdje ću ostaviti ovaj dio prazan.

774
00:45:50,490 --> 00:45:52,430
I sada izbor vrsta.

775
00:45:52,430 --> 00:45:56,010
Izbor vrsta su me čupanjem najmanji osobu iznova i iznova.

776
00:45:56,010 --> 00:45:58,380
I što smo rekli prikazivati ​​vrijeme to bio?

777
00:45:58,380 --> 00:46:00,590
To je bio n kvadrat u najgorem slučaju.

778
00:46:00,590 --> 00:46:05,220
I, nažalost, u najboljem slučaju to je također n kvadratna

779
00:46:05,220 --> 00:46:08,840
jer nemam svojevrsnu sveznajućeg pogledom na cijeli svijet;

780
00:46:08,840 --> 00:46:13,140
Znam samo na punom iteraciji da sam doista našli najmanji osobu.

781
00:46:13,140 --> 00:46:15,860
Dakle, izbor vrsta vrsta sranje u tom smislu,

782
00:46:15,860 --> 00:46:17,920
ali naopako je da je to vrsta intuitivno.

783
00:46:17,920 --> 00:46:21,470
To je prilično lako kodirati gore, jer sve što morate učiniti je napisati nekoliko ugniježđena za petlje,

784
00:46:21,470 --> 00:46:24,620
obično, koja prolazi kroz potrazi za najmanji element

785
00:46:24,620 --> 00:46:27,840
a zatim stavlja najmanji element gdje pripada na kraju popisa.

786
00:46:27,840 --> 00:46:29,900
Dakle, ni tu će biti trade-off.

787
00:46:29,900 --> 00:46:34,440
Iznos od vremena koje je potrebno da mislite i da se zapravo razviti nešto pisanjem koda

788
00:46:34,440 --> 00:46:39,460
mogao vrlo dobro uzeti više vremena ako želite bolji algoritam i brže performanse.

789
00:46:39,460 --> 00:46:41,780
>> Ali ako doista samo vrsta koda nešto brzo i prljavo

790
00:46:41,780 --> 00:46:45,000
i samo vrsta uzeti najgluplji mogući ideju možete sjetiti,

791
00:46:45,000 --> 00:46:47,580
koja bi mogla odvesti nekoliko minuta koda, ali s velikim skupovima podataka

792
00:46:47,580 --> 00:46:49,580
vaš algoritam bi moglo potrajati satima pokrenuti.

793
00:46:49,580 --> 00:46:51,690
I čak sam u dodiplomskoj školi ponekad bi ove ustupke.

794
00:46:51,690 --> 00:46:55,660
To bi bilo 03:00, bio sam pokušava analizirati neke vrlo veliki skup podataka

795
00:46:55,660 --> 00:46:59,650
odnose na sigurnost istraživanja radim, i to bilo je provesti pet minuta

796
00:46:59,650 --> 00:47:03,210
prilagoditi svoj program za analizu podataka i ići na spavanje

797
00:47:03,210 --> 00:47:08,420
ili provesti osam sati uzimajući ga samo pravo, tako da radi odmah, a ne ići na spavanje.

798
00:47:08,420 --> 00:47:10,530
I tako tamo to je vrsta svjesne odluke.

799
00:47:10,530 --> 00:47:12,740
Manje vrijeme razvoja, više sna.

800
00:47:12,740 --> 00:47:14,780
U retrospektivi, ja vjerojatno ne bi trebalo poticati da

801
00:47:14,780 --> 00:47:19,120
kada je cilj je da se ovdje optimizirati kvalitetu kodeksa,

802
00:47:19,120 --> 00:47:21,280
ali da je u stvarnom svijetu je vrlo razuman kompromis.

803
00:47:21,280 --> 00:47:25,130
Manje vremena, manje performanse ili obrnuto.

804
00:47:25,130 --> 00:47:28,110
Dakle, ovdje smo konačno dobili priliku za razgovor o theta.

805
00:47:28,110 --> 00:47:32,830
Theta zapis je nešto računalni znanstvenici mogu dovesti u razgovoru

806
00:47:32,830 --> 00:47:36,160
kada veliki O i omega dogoditi da bude isti.

807
00:47:36,160 --> 00:47:40,160
Kažeš theta stvarno poslati poruku da je to vrsta čvrsto vezan.

808
00:47:40,160 --> 00:47:43,340
Bez obzira da li je scenarij dobar ili loš, to je n kvadratna.

809
00:47:43,340 --> 00:47:46,510
Dakle, to jednostavno nije relevantno u ovim pričama ovdje.

810
00:47:46,510 --> 00:47:48,560
Ubacivanje vrsta je posljednji smo gledali,

811
00:47:48,560 --> 00:47:50,830
gdje sam bio samo umetanjem svima na pravom mjestu.

812
00:47:50,830 --> 00:47:54,930
U najboljem slučaju ono što je trčanje vrijeme unosa vrste kao što smo vidjeli ovdje?

813
00:47:54,930 --> 00:47:57,250
[Student] najboljem slučaju? >> Najboljem slučaju.

814
00:47:57,250 --> 00:48:00,100
>> To je n, jer u najboljem slučaju svi poredani,

815
00:48:00,100 --> 00:48:02,580
i Sammy i nitko drugi stvarno morao premjestiti na sve.

816
00:48:02,580 --> 00:48:04,610
Oni su već u svoje pravo mjesto.

817
00:48:04,610 --> 00:48:08,570
Dakle umetanja vrsta u najboljem slučaju, u ovom slučaju, n.

818
00:48:08,570 --> 00:48:12,770
No, u najgorem slučaju to je vrsta n kvadratna. Zašto?

819
00:48:12,770 --> 00:48:16,230
Ako moj popis ljudi je u obrnutom redoslijedu,

820
00:48:16,230 --> 00:48:21,260
Prvi put sam početi s brojem 8, a ja mu umetnuti ili ju u pravilnom položaju, što je upravo ovdje.

821
00:48:21,260 --> 00:48:25,270
Nekako mi premjestiti na strani. Ovi momci su nesortirani, on ili ona je riješeno.

822
00:48:25,270 --> 00:48:28,970
Ali sada sam se dogoditi da vam tko sljedeći? >> [Student] 7.

823
00:48:28,970 --> 00:48:31,250
7 u najgorem slučaju, jer je to u obrnutom redoslijedu.

824
00:48:31,250 --> 00:48:34,920
>> Dakle, ovdje je sedam. Odakle 7 pripadaju? Definitivno iza mene.

825
00:48:34,920 --> 00:48:39,460
Ali sada 7 zapravo ne pripada odmah iza mene, ali iza broja 8,

826
00:48:39,460 --> 00:48:41,880
pa moram reći: "Oprosti, broj 8, može li molim vas premjestiti na ovaj način

827
00:48:41,880 --> 00:48:44,640
"Kako bi napravili mjesta za sedam?" Sada sam susret 6.

828
00:48:44,640 --> 00:48:48,530
"Oh, oprostite, broj 8 i broj 7, možete premjestiti kako bi napravili mjesta za šest?"

829
00:48:48,530 --> 00:48:52,360
Dakle, drugim riječima, s ugradnjom vrste, iako ja ne radim puno kretanja,

830
00:48:52,360 --> 00:48:56,330
ljudi iza mene rade puno više posla, te da je dobio koštati netko vrijeme.

831
00:48:56,330 --> 00:48:58,000
To će koštati računalo vrijeme.

832
00:48:58,000 --> 00:49:01,450
Dakle, u slučaju unosa vrsta još uvijek pate.

833
00:49:01,450 --> 00:49:06,260
Ako počnete zbrajanjem ukupnog broja koraka, mi završiti udarajući grubo n kvadratna

834
00:49:06,260 --> 00:49:11,160
jer ti dečki moraju napraviti mjesta za ljudsko biti umetnuta natrag u tom popisu.

835
00:49:11,160 --> 00:49:15,960
I tako, u ovom slučaju theta je samo ne odnosi se na određenu priču pri ruci.

836
00:49:15,960 --> 00:49:21,100
To je sve lijepo i dobro. Imamo ove tri različite načine govore o trajanju.

837
00:49:21,100 --> 00:49:26,370
No, što to zapravo znači u stvarnom smislu, ako smo zapravo pokušati kodirati do algoritam?

838
00:49:26,370 --> 00:49:31,620
>> Dopustite mi predložiti da postoji još bolji algoritam vani

839
00:49:31,620 --> 00:49:33,740
da sama ima neke ustupke.

840
00:49:33,740 --> 00:49:36,890
Mi ćemo ga nazvati spojiti vrsta, a to je vrsta ovog čarobnog algoritma

841
00:49:36,890 --> 00:49:42,840
samo da radi brže nekako, i to je tako lako izraziti, barem u pseudocode.

842
00:49:42,840 --> 00:49:46,900
Provedba ove vrste algoritma spajanja će biti kao što slijedi.

843
00:49:46,900 --> 00:49:50,860
Kada si dao n elemenata - N brojeva, n ljude, bez obzira na - prvi postoji razum ček.

844
00:49:50,860 --> 00:49:56,340
Ako je n manji od 2, spajanje vrsta samo zaustavlja. To vraća, da se tako izrazim.

845
00:49:56,340 --> 00:50:00,830
Zašto bi se zaustaviti ako je n manje od dva? >> [Nečujno učenik odgovor]

846
00:50:00,830 --> 00:50:04,480
Točno. I opet, n nije broj na popisu, n je veličina popisa.

847
00:50:04,480 --> 00:50:07,660
Ako je n manji od 2, to znači da je popis ili 1,

848
00:50:07,660 --> 00:50:09,640
gdje se očito ste razvrstani ako je jedan broj,

849
00:50:09,640 --> 00:50:11,710
ili 0, u kojem slučaju nema ništa za sortiranje,

850
00:50:11,710 --> 00:50:13,570
tako da ćemo morati ovu vrstu baze slučaju.

851
00:50:13,570 --> 00:50:20,350
Ako popis je tako kratko da postoji samo ništa učiniti, doslovno ne rade ništa. Povratak.

852
00:50:20,350 --> 00:50:25,090
Inače sortirati lijevu polovicu elemenata, a zatim sortirati desnu polovicu elemenata,

853
00:50:25,090 --> 00:50:27,410
onda spojiti dvije sortirane polovice.

854
00:50:27,410 --> 00:50:32,130
>> Ova vrsta se čini kao malo varati pri čemu te pitam kako sortirati elemente

855
00:50:32,130 --> 00:50:34,900
i ti si mi reći, "Sortirajte lijevu polovicu, sortirati desnu polovicu."

856
00:50:34,900 --> 00:50:37,240
Ja sam kao, "sve u redu. Kako sortirati lijevu polovine?"

857
00:50:37,240 --> 00:50:40,670
"Sortirajte lijevu polovicu lijeve polovice, sortirati desnu polovicu lijeve polovice, a zatim učinio."

858
00:50:40,670 --> 00:50:44,060
Vi ste vrsta ciklički definiranje što to znači za sortiranje,

859
00:50:44,060 --> 00:50:46,790
ali ispada da je zapravo sjajan u ovom slučaju.

860
00:50:46,790 --> 00:50:50,230
To nije doista to začarani krug koji nikada ne prestaje

861
00:50:50,230 --> 00:50:52,550
jer to ne prestaje kada? >> [Student] Kada dođete do 1 stvar.

862
00:50:52,550 --> 00:50:54,220
Kada dođete do 1 stvar.

863
00:50:54,220 --> 00:50:57,850
Dakle, iako ste mogli početi s osam ljudi, a ja kažem, "Sortirajte lijevu polovicu tih ljudi,

864
00:50:57,850 --> 00:51:00,480
ove četiri osobe ", onda ja kažem," Kako sortirati lijevu polovine? "

865
00:51:00,480 --> 00:51:03,450
"Pa, sortirati 2 ljudi ovdje." A onda ste poput, "U redu, u redu."

866
00:51:03,450 --> 00:51:05,520
"Kako sortirati lijevu polovicu tih ljudi?"

867
00:51:05,520 --> 00:51:09,040
"Samo sortirati ovo jedna osoba ovdje." Što je briljantan otkrivenje sada?

868
00:51:09,040 --> 00:51:13,050
Moram izdvojiti jednog čovjeka. Gotovo. Ja ne moram ništa raditi.

869
00:51:13,050 --> 00:51:16,580
Ali sada moram sortirati tu osobu, ali oni su jedna osoba, ništa učiniti.

870
00:51:16,580 --> 00:51:21,490
>> Dakle, očito je magija u ovom trećem koraku: spajanje sortirane polovice.

871
00:51:21,490 --> 00:51:25,770
Dakle spojiti vrsta traje ovaj sjajan uvid da ako break veliki problem dolje

872
00:51:25,770 --> 00:51:28,650
u dvije manje, identično veličine problema

873
00:51:28,650 --> 00:51:32,710
a zatim samo vrsta ljepila manji rješenja zajedno na kraju,

874
00:51:32,710 --> 00:51:34,720
Ja predlažem da možemo učiniti mnogo, mnogo bolje [kuckanje zvuk]

875
00:51:34,720 --> 00:51:38,050
od bilo kakve odabira ili unosa vrste.

876
00:51:38,050 --> 00:51:40,690
Ja sam zapravo bio ignorirajući da je za pola sata, ali ja stvarno ne znam što se događa

877
00:51:40,690 --> 00:51:45,040
izvan danas. [Whirring zvuk] [smijeh]

878
00:51:45,040 --> 00:51:49,660
Dakle, neka je vidjeti ako možemo vidjeti ovaj uz malu pomoć od našeg prijatelja Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Postoje dvije velike korake u procesu spajanja vrste.

880
00:51:52,810 --> 00:51:56,400
Prvo, kontinuirano podijeliti popis šalice na polovice

881
00:51:56,400 --> 00:51:59,610
dok imamo hrpu liste sa samo jednom šalicom u njima.

882
00:51:59,610 --> 00:52:02,150
Ne brinite ako popis sadrži neparan broj

883
00:52:02,150 --> 00:52:04,830
i ne možete napraviti savršeno čisti rez između njih.

884
00:52:04,830 --> 00:52:08,740
Samo proizvoljno odabrati koji popis uključiti dodatni šalicu u.

885
00:52:08,740 --> 00:52:11,320
Tako ćemo podijeliti ove liste.

886
00:52:12,420 --> 00:52:14,570
Sada imamo dvije liste.

887
00:52:18,930 --> 00:52:20,930
Sada imamo četiri liste.

888
00:52:25,730 --> 00:52:28,740
Sada imamo osam liste s jednom šalicom u svakom popisu.

889
00:52:28,740 --> 00:52:31,520
Dakle, to je to za 1. koraku.

890
00:52:31,520 --> 00:52:37,280
Za korak dva smo puta spojiti parove popisima pomoću spajanja algoritam smo naučili prije.

891
00:52:37,280 --> 00:52:44,320
Stapanje 108 i 15 smo završili s popisa 15, 108.

892
00:52:45,240 --> 00:52:51,330
Stapanje 50 i 4 smo završili s 4, 50.

893
00:52:51,330 --> 00:52:56,950
Spajanje 8 i 42 smo završili s osam, 42.

894
00:52:57,790 --> 00:53:04,360
A spajanjem 23 i 16 smo završili s 16, 23.

895
00:53:04,360 --> 00:53:08,030
Sada svi naši popisi su veličine dva.

896
00:53:08,030 --> 00:53:10,980
Primijetite da svaka od 4 lista je sortiran,

897
00:53:10,980 --> 00:53:14,230
tako da možemo početi spajanjem parova popisima ponovno.

898
00:53:14,230 --> 00:53:22,150
Stapanje 15 i 108 i 4 i 50 smo prvi uzeti 4, zatim 15,

899
00:53:22,150 --> 00:53:26,250
zatim 50, a zatim 108.

900
00:53:26,250 --> 00:53:33,020
Spajanje 8, 42 i 16, 23 mi prvo uzeti 8, zatim 16,

901
00:53:33,020 --> 00:53:37,170
zatim 23, a zatim 42.

902
00:53:37,170 --> 00:53:42,490
Tako sada imamo samo dvije liste veličine 4, od kojih je svaki razvrstani.

903
00:53:42,490 --> 00:53:45,940
Dakle, sada smo spojiti ove dvije liste.

904
00:53:45,940 --> 00:53:54,230
Prvo smo uzeti 4, onda uzmemo 8, onda mi se 15

905
00:53:54,230 --> 00:54:05,280
i 16 i 23 i 42 i 50 i 108.

906
00:54:05,280 --> 00:54:09,020
I mi smo gotovi. Mi sada imamo sortirani popis.

907
00:54:09,020 --> 00:54:13,740
>> Rob je vrsta iskorištavanjem nešto što još nismo učinili.

908
00:54:13,740 --> 00:54:16,540
To je bio predložen, ali mi nije zapravo to učiniti.

909
00:54:16,540 --> 00:54:19,230
On je radio nešto fizički sa šalicama koja sugerira

910
00:54:19,230 --> 00:54:23,680
on je proveo neko resurs osim vremena. >> [Student] Space. >> To je bio prostor.

911
00:54:23,680 --> 00:54:27,360
Činjenica da je imao ovu vrstu dvorazinskog stola gdje je imao prostora ovdje

912
00:54:27,360 --> 00:54:31,960
i prostor ovdje je zapravo implicira da je on pomoću dvostruko puno prostora

913
00:54:31,960 --> 00:54:36,390
kao i bilo koji od naših algoritama dosad - umetanje vrsta, balon sortiranje ili odabir vrsta -

914
00:54:36,390 --> 00:54:40,780
ali on je uložio ovaj dodatni prostor za takve stvari se preseliti natrag i naprijed

915
00:54:40,780 --> 00:54:42,600
dok je čuvanje stvari u red.

916
00:54:42,600 --> 00:54:47,540
I iako se osjeća kao da smo došli do sortirani popis, da se osjećao kao da je neko vrijeme.

917
00:54:47,540 --> 00:54:51,060
U stvarnosti, ono što je Rob bio događaj bio upravo ovaj algoritam.

918
00:54:51,060 --> 00:54:56,780
On je prvi uzeo problem veličine n, podijeljen u lijevoj polovici i desne polovine.

919
00:54:56,780 --> 00:54:59,380
To je kada je preselio u čaše. Zatim je ponovio taj proces.

920
00:54:59,380 --> 00:55:03,390
On je podijeljen u četiri dva seta dva ovamo i ovamo.

921
00:55:03,390 --> 00:55:08,520
Zatim je ponovio taj proces i podijeliti dva u dva seta jedan za svaki od tih različitih šalica.

922
00:55:08,520 --> 00:55:11,000
A to je gdje je briljantan ukaže prilika.

923
00:55:11,000 --> 00:55:15,840
U tom trenutku u priči, Rob je imao osam popise veličine 1,

924
00:55:15,840 --> 00:55:18,860
svi koji su razvrstani već.

925
00:55:18,860 --> 00:55:20,630
>> Pa što onda je on nastaviti raditi?

926
00:55:20,630 --> 00:55:25,260
Parne uzeo ovu sortirani popis i ovaj sortirani popis te ih spojio.

927
00:55:25,260 --> 00:55:28,200
Zatim je uzeo ovaj jedan, te ih spojio, onda je ovo jedan te ih spojio,

928
00:55:28,200 --> 00:55:30,670
onda je to jedno te ih spojio.

929
00:55:30,670 --> 00:55:32,390
A onda ono što je on učinio sljedeći?

930
00:55:32,390 --> 00:55:36,580
On je tada ponovno spojio veće popise, a zatim ponovno spojio veće popise.

931
00:55:36,580 --> 00:55:41,170
A ako mislite o tome samo intuitivno, za sada, što je on zapravo radi?

932
00:55:41,170 --> 00:55:45,450
On je dijeljenjem problem na pola, na pola, na pola, na pola

933
00:55:45,450 --> 00:55:47,600
kako bi se ove super male liste.

934
00:55:47,600 --> 00:55:51,290
Tada je vrsta kombiniranja dvokrevetna, dupli, dvokrevetna, dupli.

935
00:55:51,290 --> 00:55:54,120
Tako je radio duplo više rada, kao što smo vidjeli dosad

936
00:55:54,120 --> 00:55:56,930
s bilo koje uključuju podijeli pa vladaj, ali nije velika stvar.

937
00:55:56,930 --> 00:55:59,630
Dva puta koliko je rad nije tako velika stvar. To je samo konstantan faktor.

938
00:55:59,630 --> 00:56:03,920
I baš kao i naše aritmetičkog izraza prije, ja samo idem prijeći iz stalne čimbenike

939
00:56:03,920 --> 00:56:10,170
poput puta dva. Koga briga? Ako je 2 milijarde puta dva, to je još uvijek puno koraka.

940
00:56:10,170 --> 00:56:13,160
Dakle, ovo spajanje korak čini se da je ključni uvid.

941
00:56:13,160 --> 00:56:17,000
Idemo prošetati kroz ovo samo brojčano prije - Oh, to je ne biti nastavljen još.

942
00:56:17,000 --> 00:56:22,890
Idemo prošetati kroz ovu numerički samo zapravo vidjeti kako se to igra.

943
00:56:22,890 --> 00:56:25,940
To je uglavnom samo malo jadnog čovjeka animacija.

944
00:56:25,940 --> 00:56:27,750
Hajdemo predložiti ovo.

945
00:56:27,750 --> 00:56:31,480
Trčanje vrijeme spajanja vrste - samo trebamo način govori o tome.

946
00:56:31,480 --> 00:56:34,380
Ovo nije matematika, to je samo vrsta jezgrovit način izražavanja sebe.

947
00:56:34,380 --> 00:56:39,080
Dakle, T predstavlja vrijeme i n predstavlja što? >> [Student] veličina -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] veličina problema, broj ljudi.

949
00:56:41,400 --> 00:56:45,470
Tako sam tvrdeći da trčanje vrijeme za sortiranje n ljudi će biti 0 iznos od vrijeme

950
00:56:45,470 --> 00:56:50,290
ako je n manje od dva, jer ako imate jedan pehar ili nema kupova, nemate ništa za sortiranje.

951
00:56:50,290 --> 00:56:55,160
Ali općenito, ja ću predložiti da trčanje vrijeme za sortiranje n elemenata

952
00:56:55,160 --> 00:56:59,350
će biti vrijeme koje je potrebno za sortiranje lijevu polovina plus Desna polovina

953
00:56:59,350 --> 00:57:03,110
plus - što je to dodatni + n? >> [Student] Spajanje vrsta.

954
00:57:03,110 --> 00:57:07,260
[Malan] To je zapravo spajanje, jer ako imate N / 2 elemenata ovdje

955
00:57:07,260 --> 00:57:11,500
i imate N / 2 elemenata ovdje, koliko vremena je potrebno da ih spojiti?

956
00:57:11,500 --> 00:57:15,050
Baš kao i Rob, morate iščupati ovo ovamo, možda kidati ovamo,

957
00:57:15,050 --> 00:57:17,120
kidati ovamo, kidati ovamo, kidati ovamo.

958
00:57:17,120 --> 00:57:19,400
Morate dodirnuti svaki od šalice jednom.

959
00:57:19,400 --> 00:57:22,030
A ako ima 4 šalice plus četiri šalice, to je 8 šalice

960
00:57:22,030 --> 00:57:25,200
ili, općenitije, 8 n šalice.

961
00:57:25,200 --> 00:57:28,470
Dakle, spajanjem korak možemo izraziti kao n,

962
00:57:28,470 --> 00:57:31,330
i da doslovno uključuje nekoliko puta Rob fizički dotaknuo

963
00:57:31,330 --> 00:57:33,410
jedan od onih stiropor čaše.

964
00:57:33,410 --> 00:57:35,850
Dakle, ajmo sad napraviti proizvoljan primjer.

965
00:57:35,850 --> 00:57:41,850
Ako postoji 16 šalice, što je trčanje vrijeme sortiranja, pomoću Rob je algoritam, 16 šalice?

966
00:57:41,850 --> 00:57:44,710
To je dva puta iznos od vrijeme potrebno za sortiranje 8 šalice

967
00:57:44,710 --> 00:57:46,920
jer imamo 8 šalice ovdje, 8 šalice ovdje.

968
00:57:46,920 --> 00:57:51,520
Ne znam koliko dugo da traje, tako da smo ga generaliziranja kao T za trenutak.

969
00:57:51,520 --> 00:57:53,320
Tko zna što je to?

970
00:57:53,320 --> 00:57:58,990
Ali sada mogu sortirati od rekurzivno ili više puta pitati isto pitanje.

971
00:57:58,990 --> 00:58:01,920
Koliko vremena je potrebno izdvojiti osam šalica?

972
00:58:01,920 --> 00:58:07,030
8 šalice idem reći uzima iznos od vrijeme potrebno za sortiranje 4 šalice plus četiri čaše,

973
00:58:07,030 --> 00:58:08,880
zatim ih spajanja.

974
00:58:08,880 --> 00:58:13,080
Fine. Mi smo ušli u ciklusu već. Koliko dugo je potrebno za sortiranje 4 šalice?

975
00:58:13,080 --> 00:58:19,150
Vrijeme koje je potrebno izdvojiti četiri šalice je 2 šalice plus 2 šalice sortiranje plus spajanjem proces.

976
00:58:19,150 --> 00:58:21,440
Fine. Koliko dugo je potrebno za sortiranje dvije čaše?

977
00:58:21,440 --> 00:58:26,290
2 šalice je iznos od vrijeme potrebno za sortiranje 1 šalicu plus vrijeme koje je potrebno riješiti još jednu šalicu

978
00:58:26,290 --> 00:58:29,040
plus iznos od vrijeme potrebno za spajanje, što je samo dvije.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Zadnje pitanje. Koliko dugo je potrebno za sortiranje 1 šalicu?

980
00:58:33,340 --> 00:58:37,260
Ovdje je osnovni slučaj da smo predviđali da ćemo pogoditi ranije.

981
00:58:37,260 --> 00:58:42,250
Činjenica da je potrebno ne rade uopće sortirati najmanji od problema

982
00:58:42,250 --> 00:58:44,120
znači da je sada, vrsta razreda škole stilu,

983
00:58:44,120 --> 00:58:46,460
možemo ići započeti uključivanjem ove brojeve natrag u.

984
00:58:46,460 --> 00:58:50,630
Mi sada znamo što T 1. je, tako da ja mogu priključiti 0 za T iz jedne.

985
00:58:50,630 --> 00:58:54,420
To će mi dati odgovor na T iz dva, što sam onda možete priključiti u viši.

986
00:58:54,420 --> 00:58:56,930
To će mi dati t 4, što ja mogu priključiti u viši.

987
00:58:56,930 --> 00:58:58,920
To će mi dati t 8, što ja mogu priključiti u viši.

988
00:58:58,920 --> 00:59:04,330
A ako ja zapravo radim na to da matematiku uključivanjem u tim odgovorima,

989
00:59:04,330 --> 00:59:08,590
I onda se T od 16 je 64.

990
00:59:08,590 --> 00:59:12,090
A što predstavlja 64?

991
00:59:12,090 --> 00:59:15,700
Ako je T 16, yeah, to je 16 puta četiri.

992
00:59:15,700 --> 00:59:20,120
Dakle, ja tvrdim da sada prikazivati ​​vrijeme ovu stvar zove spojiti vrsta -

993
00:59:20,120 --> 00:59:22,590
i to će biti fanciest od onih koje smo vidjeli dosad -

994
00:59:22,590 --> 00:59:26,160
će se zvati n log n

995
00:59:26,160 --> 00:59:31,140
jer koliko puta možete Rob podijeliti hrpu šalica u poluvremenu? Prijavite n.

996
00:59:31,140 --> 00:59:34,370
To je isto kao npr. telefonskog imenika, to je isto kao self-prebrojavanja primjer.

997
00:59:34,370 --> 00:59:36,380
>> Koliko puta možete podijeliti nešto na pola?

998
00:59:36,380 --> 00:59:38,410
Međutim, tu je ovo spajanje korak.

999
00:59:38,410 --> 00:59:42,920
Možda ćete morati podijeliti čaše na pola opet i opet i opet,

1000
00:59:42,920 --> 00:59:45,640
ali svaki put ćete morati spojiti.

1001
00:59:45,640 --> 00:59:48,270
I što smo ranije rekli da spajanjem n šalice traje n koraka

1002
00:59:48,270 --> 00:59:52,060
jer morate iščupati šalicu, iskopaj šalicu, a vi morate dotaknuti svaku šalicu jednom,

1003
00:59:52,060 --> 00:59:53,510
baš kao i Rob učinio.

1004
00:59:53,510 --> 00:59:59,430
Dakle, ako radimo nešto dnevnik n puta i radimo n stvari na svakom od tih iteracija,

1005
00:59:59,430 --> 01:00:03,090
svaki od tih halvings, imamo n puta log n.

1006
01:00:03,090 --> 01:00:07,220
Dakle, ako smo priključiti 16 u ovom primjeru, 16 puta prijaviti od 16. -

1007
01:00:07,220 --> 01:00:10,600
Ne brinite o tome zašto je to slučaj za sada, jer nisam privukao bazu -

1008
01:00:10,600 --> 01:00:16,100
ali log bazu 2. 16 je 4, 16 puta 4 je 64.

1009
01:00:16,100 --> 01:00:22,350
No, s druge strane, ako smo imali koristi mjehurić vrsta ili odabir sortiranja ili umetanje sortiranje s 16 brojeva,

1010
01:00:22,350 --> 01:00:26,420
što bi trajanje bilo, ako je n 16?

1011
01:00:26,420 --> 01:00:33,310
To će biti 16 kvadratna, što je 256, što je čak i ako niste sasvim slijedio sve matematiku,

1012
01:00:33,310 --> 01:00:38,390
256 je veća od 64. To je stvarno čarobna takeaway ovdje.

1013
01:00:38,390 --> 01:00:41,990
I shvatili da rade kroz to u manjim primjerima kao što će na pset

1014
01:00:41,990 --> 01:00:44,260
sve to čini puno više intuitivno.

1015
01:00:44,260 --> 01:00:49,070
No, što to zapravo znači u smislu dojam ovog algoritma je ovo:

1016
01:00:49,070 --> 01:00:54,520
Ako pogledamo spajanja sortiraj ovdje - neka mi ga podići u ovom prozoru ovdje -

1017
01:00:54,520 --> 01:00:58,560
ovo je malo drugačiji primjer gdje imamo sve tri od tih algoritama -

1018
01:00:58,560 --> 01:01:01,440
balon, izbor, i spajanje - samo rame uz rame.

1019
01:01:01,440 --> 01:01:03,740
>> Oni su svi počeli sa slučajnim rešetaka, i to je dobro.

1020
01:01:03,740 --> 01:01:06,240
Nitko nema temeljnu prednost nad drugima.

1021
01:01:06,240 --> 01:01:09,500
Idem u trenutku kliknite svaki od tih animacije - Start, Start, Start -

1022
01:01:09,500 --> 01:01:13,270
kao brz kao što sam ja, tako da, otprilike, svi oni početi u isto vrijeme,

1023
01:01:13,270 --> 01:01:17,450
i neka je uzeti u obzir da Bubble Sortiraj je gore slučaj prikazivati ​​vrijeme je ono? >> [Student] N kvadrat.

1024
01:01:17,450 --> 01:01:21,560
N kvadrat. IZBOR Poredaj najgori slučaj pokrenut je vrijeme? N kvadrat.

1025
01:01:21,560 --> 01:01:25,150
I pisma vrsta je očito - čak i ako nije sasvim slijediti sve matematiku sada,

1026
01:01:25,150 --> 01:01:30,610
to će postati mnogo više intuitivno vremenom - je, tvrdimo, n puta log n.

1027
01:01:30,610 --> 01:01:35,210
I zato log n je strogo manje od n jednom imamo velike brojeve,

1028
01:01:35,210 --> 01:01:40,230
n puta log n je manji od n puta n ili n kvadratna.

1029
01:01:40,230 --> 01:01:44,410
Dakle, što je to osjećaj da zapravo biti bolji algoritam u smislu trčanje vremena,

1030
01:01:44,410 --> 01:01:50,380
n puta log n za razliku n kvadrata? Ovdje ćemo ići. Klik, klik, klik.

1031
01:01:55,690 --> 01:01:58,650
>> To je ono što znači da koriste nešto poput spajanja vrste.

1032
01:01:58,650 --> 01:02:01,680
Imamo trenutak. Idemo vidjeti što se ovdje događa.

1033
01:02:09,440 --> 01:02:12,440
[Nasmijao] Čiji je novac na bubble vrste?

1034
01:02:14,960 --> 01:02:16,730
To već ovisi o ulazu ponekad.

1035
01:02:16,730 --> 01:02:18,120
Idemo vidjeti.

1036
01:02:18,120 --> 01:02:23,320
Hajde. To se osjeća kao da je sustiže. >> [Student] Idi, mjehurić vrsta!

1037
01:02:23,320 --> 01:02:27,370
[Studenti mrmljajući]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Da, da.

1039
01:02:29,120 --> 01:02:34,520
[Studenti mrmljajući] Idi, idi, idi!

1040
01:02:37,210 --> 01:02:40,450
[Svi navijaju] [pljesak]

1041
01:02:40,450 --> 01:02:46,240
Dakle, sada sa jednom zadnji, konačni demo, ako je malo lukav da zamotate svoj um oko matematike

1042
01:02:46,240 --> 01:02:49,280
ili vrsta vizualizacije tamo, zapravo možete čuti brzine

1043
01:02:49,280 --> 01:02:51,000
različitih algoritama drugačije.

1044
01:02:51,000 --> 01:02:53,900
Ovo je animacija je netko napravio da zapravo suradnici zvuči

1045
01:02:53,900 --> 01:02:56,980
s procesom zamjene i visina od barova.

1046
01:02:56,980 --> 01:03:00,440
Kao što ćemo vidjeti ovdje, tu je još nekoliko sortiranje algoritmi vani da su ljudi mislili.

1047
01:03:00,440 --> 01:03:03,660
Ovaj prvi će biti umetanje vrsta, a to će letjeti kroz

1048
01:03:03,660 --> 01:03:07,090
i vam dati zvučni osjećaj kako su ovi raznih algoritama rada.

1049
01:03:07,090 --> 01:03:09,080
Ovdje je umetanje vrsta.

1050
01:03:09,080 --> 01:03:18,410
[Elektronička bip]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble vrsta.

1052
01:03:20,730 --> 01:03:46,850
[Brže elektronički bip]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Izbor vrsta.

1054
01:03:48,950 --> 01:04:03,580
[Brže elektronički bip]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Spajanje vrsta.

1056
01:04:05,770 --> 01:04:17,270
[Elektronička bip]

1057
01:04:17,270 --> 01:04:20,180
[Bip usporava] [smijeh]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome vrsta.

1059
01:04:22,590 --> 01:04:38,580
[Elektronička bip]

1060
01:04:39,740 --> 01:04:46,150
>> Ovo je CS50. Vidimo se sljedeći tjedan. [Pljesak i navijanje]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]