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

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

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

4
00:00:07,130 --> 00:00:11,010
>> V redu. Dobrodošel nazaj. To je CS50 in to je konec tedna 3.

5
00:00:11,010 --> 00:00:14,680
>> Torej za tiste, ki ne poznajo, lani začel Harvard, kar se imenuje Innovation Lab,

6
00:00:14,680 --> 00:00:18,530
ali i-laboratorij, ki je čudovita stavba čez reko na univerzi v HBS

7
00:00:18,530 --> 00:00:22,640
ki je odprt za študente, dijake, študente GSA iz vsega kampusu,

8
00:00:22,640 --> 00:00:27,000
vključno s fakultete, in to je kraj, da pridejo skupaj za delo na inovativne stvari,

9
00:00:27,000 --> 00:00:29,180
zlasti podjetniške stvari

10
00:00:29,180 --> 00:00:33,410
če in 0 ali več prijatelji razmišljate o tem kaj podjetniške

11
00:00:33,410 --> 00:00:37,080
niti v tem razredu, po tem razredu, ali pa še dlje.

12
00:00:37,080 --> 00:00:41,540
>> Torej ena od stvari, ki jih storijo v obdobju J je ta izlet,

13
00:00:41,540 --> 00:00:44,510
od katerih je ena v New York, od katerih je Silicijevi dolini.

14
00:00:44,510 --> 00:00:47,530
Vesolje je zelo omejena, vendar je možnost, da Masiranje ramena z MBA

15
00:00:47,530 --> 00:00:52,200
in podiplomski študenti po kampusu in dejansko preživeti nekaj časa na teh področjih, za katera

16
00:00:52,200 --> 00:00:55,500
klepetali do novih podjetij, klepet podjetniki in podobno.

17
00:00:55,500 --> 00:00:57,870
Torej, če zanima, si oglejte ta URL.

18
00:00:57,870 --> 00:01:01,220
Prav tako je na voljo na spletnih diapozitivih.

19
00:01:01,220 --> 00:01:04,610
>> Bi lahko omilijo hišno zvok samo malo?

20
00:01:04,610 --> 00:01:08,640
Če bi radi, da se nam pridružite na kosilo v petek, 13:15, v Fire & Ice, prosim glavo tam.

21
00:01:08,640 --> 00:01:11,390
Opravičilo, če je obrazec že napolnjena do takrat, ko prideš tja.

22
00:01:11,390 --> 00:01:13,750
Ampak bomo nadaljevali tradicijo naprej.

23
00:01:13,750 --> 00:01:17,350
>> Danes smo še višjo raven razprave o različnih problemih, ki jih lahko reši,

24
00:01:17,350 --> 00:01:21,330
osredotoča veliko manj, danes vsaj na kodo in še veliko več o idejah.

25
00:01:21,330 --> 00:01:24,720
Torej menite nazaj na teden, 0, ko smo trgali telefonski imenik na pol,

26
00:01:24,720 --> 00:01:28,260
Cilj je bil, da narediš nekaj, priznam, malo dramatična

27
00:01:28,260 --> 00:01:32,360
ampak za pošiljanje opozoril, da iskanje nima, da je nujno,

28
00:01:32,360 --> 00:01:35,100
kot je očitno na prvi pogled, kot si morda mislite.

29
00:01:35,100 --> 00:01:40,200
In reševanje težav na splošno ne bi nujno vedno najboljša -

30
00:01:40,200 --> 00:01:44,130
Najbolj očitna rešitev ne bi nujno najboljši.

31
00:01:44,130 --> 00:01:47,300
Tako smo imeli ta imenik in, odkrito rečeno, vsi v tej sobi je imel instinkt,

32
00:01:47,300 --> 00:01:51,470
najbolj verjetno, da bi začeli v sredini, ko iščejo Mike Smith in nato šel v levo ali desno

33
00:01:51,470 --> 00:01:54,280
temelji na katerem koli črko zgodilo, da smo končali na.

34
00:01:54,280 --> 00:01:57,560
>> Ampak to preprosto idejo, da smo ljudje za samoumevno, dokler

35
00:01:57,560 --> 00:02:00,670
Res bi se morala začeti prihajajo v ospredje svojega uma

36
00:02:00,670 --> 00:02:03,900
ker so težave, dobili veliko bolj zapleten, kot telefonski imenik,

37
00:02:03,900 --> 00:02:07,420
te iste preproste, briljantno vpogled so tisto, kar se dogaja, da se nam

38
00:02:07,420 --> 00:02:10,259
za reševanje bolj zapletenih in bolj zanimivo težave,

39
00:02:10,259 --> 00:02:12,930
med njimi nekatere stvari, ki jih jemljemo za samoumevno že v teh dneh.

40
00:02:12,930 --> 00:02:15,720
Milijarde spletnih strani tam, pa vendar Google in Bing in podobno

41
00:02:15,720 --> 00:02:17,660
so sposobni najti stvari za nas tako.

42
00:02:17,660 --> 00:02:22,300
To se ne dogaja z linearno iskanje, iskanje po vseh možnih spletnih straneh.

43
00:02:22,300 --> 00:02:25,290
Facebook je lahko povedal, kdo vse so prijatelji ali prijatelji prijateljev,

44
00:02:25,290 --> 00:02:28,250
in da se lahko tudi na videz se opravi v trenutku te dni

45
00:02:28,250 --> 00:02:30,820
čeprav imajo na milijone uporabnikov.

46
00:02:30,820 --> 00:02:34,250
>> In tako se, kako smo dejansko reševanje težav na tem merilu bo na koncu zmanjšalo

47
00:02:34,250 --> 00:02:37,830
zamislim smo pogledal v tednu 0 in malo več danes.

48
00:02:37,830 --> 00:02:42,320
Ne bomo ponovno izvedli ta algoritem, pa opozarjajo tudi storil v tednu 0 Ta vaja

49
00:02:42,320 --> 00:02:44,780
, kjer smo vsi vstali, da na številko 1,

50
00:02:44,780 --> 00:02:48,720
in potem bomo imeli vse, samo-count, ki jih seznanjanje off, dodajanje številk skupaj,

51
00:02:48,720 --> 00:02:51,930
kot polovica banda sedel na vsaki ponovitvi.

52
00:02:51,930 --> 00:02:56,750
Torej smo šli od 500 študentov v 250-125 in tako naprej.

53
00:02:56,750 --> 00:03:00,080
Toda, kot smo rekli v ponedeljek, močan ideja ni

54
00:03:00,080 --> 00:03:02,460
je bil, da če bomo podvojili velikost tega problema

55
00:03:02,460 --> 00:03:06,480
in vsi otroci iz skupnosti ali ES 10 se je vrnil v sobo in se nam je pridružil,

56
00:03:06,480 --> 00:03:09,510
No, lahko bi verjetno računajo, da se celotno skupino sestavljenega

57
00:03:09,510 --> 00:03:13,380
samo z 1 veliko več ponovitev zanke, saj bi se le morda dvojno velikost

58
00:03:13,380 --> 00:03:15,630
ali ES 10 je pri malo več kot dvakrat večja od velikosti.

59
00:03:15,630 --> 00:03:18,440
In tako bi morali porabiti malo več časa,

60
00:03:18,440 --> 00:03:22,000
vendar pa ne bi bilo treba porabiti 400 ali 700 več korakov.

61
00:03:22,000 --> 00:03:26,550
>> Samo za barvanje to sliko na način, ki je malo manj abstraktno, naj ne bi vsi vstali.

62
00:03:26,550 --> 00:03:31,100
Ampak, če tisti, ki ste se odločili, da bi sedel v orkestru danes ne bi motilo stoje,

63
00:03:31,100 --> 00:03:34,580
pa poglejmo, če lahko ugotovimo, med vami, ki najvišja oseba

64
00:03:34,580 --> 00:03:36,730
s tem enako vrsto primerjalnih algoritem.

65
00:03:36,730 --> 00:03:41,830
Torej, če si sedel v orkestru, moje opravičilo, vendar korak 1, stand up;

66
00:03:41,830 --> 00:03:44,650
2. korak, par off s kom si v bližini,

67
00:03:44,650 --> 00:03:49,360
ugotoviti, kdo je višji, in se usedi, če so krajši.

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

69
00:03:51,360 --> 00:03:56,280
[Učenci godrnjajo]

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

71
00:04:15,320 --> 00:04:19,010
Ok. Eden od njih je zapustil položaj. Kako ti je ime? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, ste najvišja oseba v oddelku orkestra danes.

73
00:04:21,959 --> 00:04:28,100
>> Čestitamo. [Ploskanje in navijanje] Ok. Imajo sedež. Tako smo ugotovili, Andrew.

74
00:04:28,100 --> 00:04:30,870
Ampak kako dolgo bi me upoštevati, na primer, da je bil Andrew

75
00:04:30,870 --> 00:04:33,740
V tem orkestru oddelku 50 + ali tako ljudi?

76
00:04:33,740 --> 00:04:36,900
Lahko bi vzel dokaj preprost pristop in začeli tukaj.

77
00:04:36,900 --> 00:04:39,270
In sem 2 ljudi je vstal in sem jih primerjajo,

78
00:04:39,270 --> 00:04:42,120
in potem sem rekel, da kdor je nekoliko krajša, "Ok, sedite,"

79
00:04:42,120 --> 00:04:44,380
in bom, da se spomnimo, kdo je višja je bila oseba.

80
00:04:44,380 --> 00:04:49,030
Potem pa ponavljam, ponavljam, ponavljam, jaz pa visijo na najvišjem osebe

81
00:04:49,030 --> 00:04:51,920
dokler ne najdem nekoga, nekoliko višji od njih, na kateri točki

82
00:04:51,920 --> 00:04:54,950
nekoliko krajša oseba je nato sedel.

83
00:04:54,950 --> 00:04:57,690
Vendar je v tem algoritmu v tem oddelku orkester, če obstaja n od tebe,

84
00:04:57,690 --> 00:05:00,480
koliko korakov je, da algoritem bo trajalo? >> [Študent] N.

85
00:05:00,480 --> 00:05:03,580
>> To se dogaja, da se n, prav, saj v najslabšem primeru, če se tako izrazim,

86
00:05:03,580 --> 00:05:09,090
najvišja oseba, ki je zadnja oseba, ki sem dobil, da samo z naključnim nesrečo.

87
00:05:09,090 --> 00:05:14,260
Torej, v najslabšem primeru, je čas delovanja tega algoritem linearna, to je n

88
00:05:14,260 --> 00:05:18,070
pri čemer je n skupno število ljudi v prostoru, velikost problema.

89
00:05:18,070 --> 00:05:19,600
Kaj je to algoritem?

90
00:05:19,600 --> 00:05:22,080
Dejstvo, da ste vsi vstali in potem spet pol ti sedel,

91
00:05:22,080 --> 00:05:23,950
polovica vas sedel, pol ti sedel.

92
00:05:23,950 --> 00:05:26,070
Koliko korakov, da bi morali sprejeti, če obstaja n izmed vas?

93
00:05:26,070 --> 00:05:30,200
[Študent] N log n. >> To bi bilo še slabše. Prijavite n.

94
00:05:30,200 --> 00:05:32,930
>> Tako se prijavite n, tudi če se ne spomnite, kaj je logaritem,

95
00:05:32,930 --> 00:05:38,410
za zdaj samo hvaležni, da gre nekako na to prepolovitev in prepolovitev in prepolovili.

96
00:05:38,410 --> 00:05:41,000
Ni nujno, da je faktor 2. To je lahko faktor 3.

97
00:05:41,000 --> 00:05:46,560
Ampak to je to ponavljanje iste vrste faktor, tako da je velikost problema se začne tukaj

98
00:05:46,560 --> 00:05:49,620
potem pa takoj gre tukaj, potem je tukaj, potem je tukaj, potem tukaj.

99
00:05:49,620 --> 00:05:53,580
Nisi majhnimi ugrizi iz problema, ste res sekanje stran na njej

100
00:05:53,580 --> 00:05:56,160
z veliko potezo vsakič.

101
00:05:56,160 --> 00:06:00,810
Tako smo imeli 50 ljudi, nato 25, nato 12 ½ ali 13 ljudi, stoji,

102
00:06:00,810 --> 00:06:05,370
nato 6 ½ in tako naprej, dokler na koncu je ostal samo Andrew položaju.

103
00:06:05,370 --> 00:06:08,710
Torej bomo za klic, da je dnevnik n, in si lahko predstavljate tako, kot sledi.

104
00:06:08,710 --> 00:06:12,570
Spomnimo to sliko tukaj, kjer linearni algoritem je kot rdečo črto tam,

105
00:06:12,570 --> 00:06:17,520
rumena linija je štetje z algoritmom 2s, ki smo jo uporabili za štetje študente

106
00:06:17,520 --> 00:06:22,300
v preteklosti, danes pa sveti gral bo ostala ta zelena črta

107
00:06:22,300 --> 00:06:25,470
če, če bomo podvojili število ljudi v orkestru oddelku ali pa je dejal,

108
00:06:25,470 --> 00:06:29,170
hudiča, imejmo vse v celotnem prostoru stand up, ni tako velik posel

109
00:06:29,170 --> 00:06:31,560
ker smo podvojila, koliko ljudi je tukaj,

110
00:06:31,560 --> 00:06:33,500
1 več ponovitev, ni problem.

111
00:06:33,500 --> 00:06:36,200
>> Ugotovili smo, Andrew ali tisti, ki se zgodi, da bo višji od Andreja

112
00:06:36,200 --> 00:06:38,770
V medetaži ali na balkonu.

113
00:06:38,770 --> 00:06:42,140
Torej, to preprosto idejo, da se je toliko za odobrene v telefonskem imeniku,

114
00:06:42,140 --> 00:06:46,170
zavedati, da obstaja toliko različnih krajev, kjer ga lahko uporabljajo.

115
00:06:46,170 --> 00:06:50,810
Samo, da slap nekaj žargonu - pravzaprav namesto žargonu prvič,

116
00:06:50,810 --> 00:06:52,750
pustite me, da te slike tukaj.

117
00:06:52,750 --> 00:06:56,970
Zdaj smo se pogovarjali o n in n / 2 in se prijavite n,

118
00:06:56,970 --> 00:07:00,500
vendar se gotovo lahko prišli do, kot bomo tekom semestra,

119
00:07:00,500 --> 00:07:05,130
druga vrsta matematičnih formul za opis tega splošnega pojma časa vožnje.

120
00:07:05,130 --> 00:07:07,580
To so izven konteksta, za zdaj, ker bomo videli kmalu

121
00:07:07,580 --> 00:07:09,900
algoritmi, ki jih dejansko predstavljajo.

122
00:07:09,900 --> 00:07:17,990
>> Opazil sem linearna linija n je premica, je pravzaprav zelo nizka kaže zdaj.

123
00:07:17,990 --> 00:07:22,950
To je neke vrste optično iluzijo, da smo samo v spremeniti tisto, kar os x predstavlja

124
00:07:22,950 --> 00:07:26,130
in os y, in lahko naredimo ravno črto točko v katerokoli smer želimo.

125
00:07:26,130 --> 00:07:30,350
A razlog, da je tako na videz ravno zdaj

126
00:07:30,350 --> 00:07:35,690
zato, ker smo potrebovali, da naredite prostor na grafu za veliko počasneje teče čas.

127
00:07:35,690 --> 00:07:39,030
Za zdaj vemo, da je nekaj zelo slabih algoritmi v življenju,

128
00:07:39,030 --> 00:07:43,790
nekateri, ki ne sprejmejo ukrepov n ali, še bolje, da se prijavite n ukrepe, vendar več.

129
00:07:43,790 --> 00:07:48,820
Torej nad črto n tu na dnu obvestila obstaja n-krat log n,

130
00:07:48,820 --> 00:07:51,410
in bomo videli, kaj to pomeni, prej ali slej.

131
00:07:51,410 --> 00:07:56,010
Predvsem, da je n kvadrat, in še nismo videli nobenega n kvadrat algoritme, vendar pa smo kmalu.

132
00:07:56,010 --> 00:07:57,660
In to zgleda res slabo.

133
00:07:57,660 --> 00:08:01,610
Tukaj je 2 do n, kar eksponentno, ki se počuti še slabše.

134
00:08:01,610 --> 00:08:05,760
In vendar, zanimivo, potem je n kubikov, ki bi, če ste nekako mislijo za naprej,

135
00:08:05,760 --> 00:08:10,000
če vrste math od 2 do n dejansko postane precej naravnost,

136
00:08:10,000 --> 00:08:15,930
precej višje od n kubikov, če pogledaš na osi dovolj daleč ven.

137
00:08:15,930 --> 00:08:19,890
Torej, opazil zdaj te osi je samovoljno 2-10 na x osi.

138
00:08:19,890 --> 00:08:21,770
>> In kaj to pomeni?

139
00:08:21,770 --> 00:08:23,890
To pomeni, da ljudje 2 do 10 ljudi v sobi.

140
00:08:23,890 --> 00:08:27,200
To je vse, kar pomeni x: velikost problema, ne glede na kontekst.

141
00:08:27,200 --> 00:08:30,420
In navpične osi zdaj je število sekund ali številu korakov -

142
00:08:30,420 --> 00:08:31,840
nekateri enota časa.

143
00:08:31,840 --> 00:08:34,740
Toda opazil, da je 0-60 in 0-10.

144
00:08:34,740 --> 00:08:38,549
Ampak, če bomo vrsta zoom out, kot si morda v Excelu ali kakem Charting programske opreme,

145
00:08:38,549 --> 00:08:43,370
in gremo do 200.000, opazil, da nekaj takega kot 2 do n

146
00:08:43,370 --> 00:08:47,520
bo povsem preplavijo tekočih čase n kvadrat,

147
00:08:47,520 --> 00:08:50,960
n kubikov, n log n - vse, kar smo govorili doslej.

148
00:08:50,960 --> 00:08:54,190
In še ulov je, ko začnete govoriti o stvareh, kot so Facebook

149
00:08:54,190 --> 00:08:57,150
kje ste mnogo, mnogo, mnogo ljudi, med seboj povezane,

150
00:08:57,150 --> 00:09:00,650
ste n ljudi, lahko vsak od njih pa ima toliko kot prijatelja n

151
00:09:00,650 --> 00:09:02,860
če so vsi nekako kolega-kolega na svetu,

152
00:09:02,860 --> 00:09:08,100
no, to je že n-krat n, da je n kvadrat možne prijateljstva,

153
00:09:08,100 --> 00:09:10,950
vsaj v 1 smer, n kvadratnih možnih prijateljstva.

154
00:09:10,950 --> 00:09:15,330
Tako, da že kaže, da išče socialni graf Facebook, če se tako izrazim,

155
00:09:15,330 --> 00:09:18,090
Lahko začnete, izražena v teh vrstah formul.

156
00:09:18,090 --> 00:09:19,820
>> Vrnili se bomo in to veliko bolj konkreten,

157
00:09:19,820 --> 00:09:23,280
ampak za zdaj je cilj v naslednjih nekaj tednih

158
00:09:23,280 --> 00:09:27,170
se dogaja, da se prepričajte, da ne bo šel o izvajanju algoritmov ali kode

159
00:09:27,170 --> 00:09:29,870
V ta namen se ob toliko časa, kot nekaj takega.

160
00:09:29,870 --> 00:09:33,110
Ampak zanimivo pri računalništvu, če boste še naprej na tem področju

161
00:09:33,110 --> 00:09:38,320
ob razrede, kot CS121 CS124,, ki sta teorija tečaji,

162
00:09:38,320 --> 00:09:41,300
je, da so dejansko nekaj problemov, ki obstajajo na tem svetu

163
00:09:41,300 --> 00:09:45,710
da je bistveno, kolikor vemo, ni mogoče rešiti hitreje

164
00:09:45,710 --> 00:09:48,880
kot najslabši od teh grafov dejansko kaže.

165
00:09:48,880 --> 00:09:53,660
Torej je veliko odprtih vprašanj na tem svetu, naj storijo veliko bolje kot ljudje, imajo doslej.

166
00:09:53,660 --> 00:09:56,130
>> Torej začnimo s tem pa na primer.

167
00:09:56,130 --> 00:09:59,650
Videli smo, Sean spopad s tem na kamero, vse preveč nerodno na video.

168
00:09:59,650 --> 00:10:05,270
Ampak dejstvo pa je bilo, ko je bil Sean nalogo pri iskanju na krovu, kot je ta številka 7,

169
00:10:05,270 --> 00:10:10,300
spomnim, da sem rekel, da "je nekje v ozadju teh kosov papirja ali bele vrata

170
00:10:10,300 --> 00:10:12,570
"Številka 7 Sean. Našli za nas."

171
00:10:12,570 --> 00:10:14,200
In bilo je čudovito nerodno gledati

172
00:10:14,200 --> 00:10:15,790
ker je bil res borila s tem problemom.

173
00:10:15,790 --> 00:10:19,720
Toda realnost je Sean naredil kot kdorkoli v sobi, bi lahko storili.

174
00:10:19,720 --> 00:10:21,890
On je malo več kot tipičen oseba lahko imela,

175
00:10:21,890 --> 00:10:24,760
vendar je domneval, da je bilo nekaj trik, da bi ta problem,

176
00:10:24,760 --> 00:10:26,590
je domneval, da mu nekaj manjka.

177
00:10:26,590 --> 00:10:29,320
In to ni pomagalo, da je na stotine oči so bile ob določitvi nanj.

178
00:10:29,320 --> 00:10:34,250
>> Ampak dejstvo pa je, če je vhodni problema je kup naključnih števil

179
00:10:34,250 --> 00:10:37,120
in ste se morali najti takšno številko 1,

180
00:10:37,120 --> 00:10:39,770
Največ kar lahko naredite, je linearna iskanje.

181
00:10:39,770 --> 00:10:44,060
Začnite na levi strani, nato v desno, ali začeti na desni, premakni v levo.

182
00:10:44,060 --> 00:10:48,300
Nazaj, bi morali razmišljati, "Sean, zakaj nisi začeti z drugega konca?"

183
00:10:48,300 --> 00:10:52,120
No lahko, 7 so prav tako lahko bil tu naključno,

184
00:10:52,120 --> 00:10:54,980
vendar sem namenoma dal tam, ker sem mislil, da ne bo začel konec.

185
00:10:54,980 --> 00:10:59,320
Tako nekako manipulira stanje, vendar pa ga Naključje 7, so lahko kjerkoli že.

186
00:10:59,320 --> 00:11:02,380
Tako se začne na desnem koncu bi lahko bilo bolje, potem,

187
00:11:02,380 --> 00:11:04,320
kaj pa, če v naslednjem letu sem premakniti 7 drugje?

188
00:11:04,320 --> 00:11:06,830
To ni popolnoma novo rešitev problema -

189
00:11:06,830 --> 00:11:10,520
začenši z 1 ali drugega konca - ko ste saj nima drugih predpostavk.

190
00:11:10,520 --> 00:11:13,620
Torej, Sean začeli iskati skozi številke in reče: "5. To ni tukaj."

191
00:11:13,620 --> 00:11:17,280
Šel sem in videl 19, nato pa je obstal za približno 20 sekund,

192
00:11:17,280 --> 00:11:22,330
Nato je odprl to za 13, nato pa je postalo jasno,

193
00:11:22,330 --> 00:11:24,270
da se ne zdi, da je vzorec tukaj.

194
00:11:24,270 --> 00:11:28,090
Ni bilo 1, 2, 3, 4 ali podobno. Ni bilo razlike v številu, ki ne pomagajo.

195
00:11:28,090 --> 00:11:32,320
In tudi dejstvo, da sem te poceni koščkov papirja, da bi prikrili številke

196
00:11:32,320 --> 00:11:35,270
je pravzaprav namerno, ker če sem odstranil vse te koščke papirja,

197
00:11:35,270 --> 00:11:38,760
večina od nas, Sean vključene, bi verjetno pogledal nekako mikroskopom

198
00:11:38,760 --> 00:11:43,410
na tablo in rekel: »Oh, 7 je očitno tam." Uspelo nam je takoj.

199
00:11:43,410 --> 00:11:46,460
>> In morda, da je način, kako se človeški možgani delujejo do neke mere,

200
00:11:46,460 --> 00:11:50,730
ampak v resnici, oči ali um je bil verjetno posnemanje številke od desne proti levi,

201
00:11:50,730 --> 00:11:55,190
od leve proti desni, srednji ven - nekaj, kar se je dogajalo fiziološko

202
00:11:55,190 --> 00:11:57,640
tako, da se mu je zdelo, kot da je v trenutku dogaja,

203
00:11:57,640 --> 00:12:01,360
vendar so možnosti, čeprav je bilo interno nekakšen metodologije za ugotavljanje 7.

204
00:12:01,360 --> 00:12:05,160
In res, zdaj, ko govorimo o poljih in podatkovnih struktur

205
00:12:05,160 --> 00:12:08,780
in spomin notranjosti računalnika, lahko edina stvar, ki smo jo tudi ljudje

206
00:12:08,780 --> 00:12:13,070
je pogled na posameznih lokacijah pomnilnika 1 naenkrat.

207
00:12:13,070 --> 00:12:16,600
>> Tako lahko vsak drugi lokaciji, kot tudi pokriti z nekaj listek

208
00:12:16,600 --> 00:12:21,170
ker ne moremo videti nekako. To lahko storimo samo 1 stvar naenkrat.

209
00:12:21,170 --> 00:12:25,030
Torej v tem primeru, v primeru, Sean, smo šli tu in potem smo šli tu

210
00:12:25,030 --> 00:12:31,040
in potem smo šli tukaj, tukaj, tukaj, tukaj, sem pameten, do konca leta

211
00:12:31,040 --> 00:12:34,450
in kar nekako preskočil tole samovoljno in ugotovil, 7 tam.

212
00:12:34,450 --> 00:12:37,470
Ta ni bil posebno posebnega. Tudi ta je bil v okvari.

213
00:12:37,470 --> 00:12:39,530
Vendar pa je končno našel 7.

214
00:12:39,530 --> 00:12:45,360
Ampak zdaj je takeaway res je, da je največ, kar lahko storite, ko noben podatek

215
00:12:45,360 --> 00:12:50,400
razen naključno razvrščeni številk je, da začnete z leve ali začnite z desne.

216
00:12:50,400 --> 00:12:54,950
Ali vraga, lahko naključno odprl vrata, vendar je tudi kaj potem to pomeni, da je naključno?

217
00:12:54,950 --> 00:12:57,220
No, jaz se moramo nekako formalizirati, kaj to pomeni, da sem začel,

218
00:12:57,220 --> 00:13:01,150
potem pa tukaj, potem kliknite tukaj. Sean naredil veliko, in to je samo zabavno gledati.

219
00:13:01,150 --> 00:13:06,340
Kaj pa, če namesto tega smo spremenili je problem malo in bruhati letošnji Seana, če bo?

220
00:13:06,340 --> 00:13:09,460
Bi kdo lahko udobno prihaja na oder in reševanje nekoliko drugačen problem

221
00:13:09,460 --> 00:13:12,330
in se pojavljajo na kamero?

222
00:13:12,330 --> 00:13:15,720
>> Pojdimo po orkestru, ker ste vi bili zelo vpleteni že danes.

223
00:13:15,720 --> 00:13:21,430
Kaj pa v roza, v klobuku? Pridi dol. Kako ti je ime? >> Alex. >> Alex. Ok.

224
00:13:21,430 --> 00:13:24,580
Tako bo Alex bo letošnji Sean in bodo v naslednjih nekaj letih

225
00:13:24,580 --> 00:13:27,770
vredno CS50 predavanj.

226
00:13:27,770 --> 00:13:30,340
Alex, lepo da sva se spoznala. >> Me veseli preveč.

227
00:13:30,340 --> 00:13:33,470
Izziv pri roki za vas je, da imate to nekoliko lažje

228
00:13:33,470 --> 00:13:38,950
v tem, da vam govorim enake številke so tu, vendar so zdaj razvrščeni.

229
00:13:38,950 --> 00:13:41,800
Torej, zdaj vaš cilj je najti številke 7.

230
00:13:41,800 --> 00:13:45,370
In dejansko bi morali res to - Ti si vrste varanje, kot računalnik ne bi,

231
00:13:45,370 --> 00:13:47,990
ga je videti, kaj je bilo število trenutek nazaj.

232
00:13:47,990 --> 00:13:50,360
S kredo to dejansko ne bo pomagalo vse to veliko,

233
00:13:50,360 --> 00:13:52,810
ampak kaj je pretvarjal, da ne veš, kaj je izvirna matrika je.

234
00:13:52,810 --> 00:13:56,600
Vse, kar vem zdaj, je, da imate niz številk, razvrščenih

235
00:13:56,600 --> 00:14:00,360
da bi lahko razlike med njimi, in vaš cilj je najti številke 7.

236
00:14:00,360 --> 00:14:05,080
Kako bi vi, razumen človek, iti o iskanju številko 7?

237
00:14:05,080 --> 00:14:07,770
>> Pojdi od nizkih do visokih? >> Redu. Pojdi nizka do visoka.

238
00:14:07,770 --> 00:14:10,990
In jih ne odtrgate. Naj jih samo dvigne, da bomo lahko znova uporabi.

239
00:14:10,990 --> 00:14:14,730
V redu, torej 1. Počakaj. Preden nadaljujem, da je 1, očitno napačna.

240
00:14:14,730 --> 00:14:17,270
Torej, kaj se dogaja po glavi potem? Kaj je vaš naslednji korak?

241
00:14:17,270 --> 00:14:23,250
Naslednji 1. >> Redu. Naslednji 1. Dobro. 3, tako napačna. Kaj je vaš naslednji korak?

242
00:14:23,250 --> 00:14:27,670
Naprej dogaja. >> Redu. Naprej dogaja. 5.

243
00:14:27,670 --> 00:14:31,110
Torej naprej dogaja, in mi izročil to za zanamce.

244
00:14:31,110 --> 00:14:35,720
7. >> Odlično. Zelo dobro. Najdeno številko 7. [Aplavz]

245
00:14:35,720 --> 00:14:39,720
Tako, da je bila dobra, ampak tudi Sean našli številko 7.

246
00:14:39,720 --> 00:14:44,490
In menim, da niste res izkoristiti to dodatno informacijo,

247
00:14:44,490 --> 00:14:47,780
to je, da so razporejene te številke.

248
00:14:47,780 --> 00:14:51,520
Tako smo lahko še boljši? Vse predloge tukaj? Ja, nazaj.

249
00:14:51,520 --> 00:14:54,710
[Študent] Binary iskanje. >> Jaz nimam pojma, kaj je binarno iskanje.

250
00:14:54,710 --> 00:14:58,030
>> [Študent] Začnite na sredini. >> Začnite na sredini. Ok. Da vidimo, če lahko pridemo tja.

251
00:14:58,030 --> 00:15:02,580
Torej, če bi namesto vas povedali začetek od sredine, pojdi naprej in odprla vrata na sredini.

252
00:15:02,580 --> 00:15:04,580
Tukaj je 8 od njih, tako da boste morali izbrati tisto, samovoljno

253
00:15:04,580 --> 00:15:09,800
rahlo v levo ali v desno. Ok. 7! [Aplavz] Zelo lepo.

254
00:15:09,800 --> 00:15:11,410
V redu, ampak ko smo se dogaja s tem?

255
00:15:11,410 --> 00:15:14,990
Recimo samo, da bi prekinil vez si je tukaj začelo

256
00:15:14,990 --> 00:15:16,670
saj bi to lahko enako zgodilo tudi.

257
00:15:16,670 --> 00:15:19,540
Samo da veste, da se je zgodilo 7 je bil tam. Torej, to je 13.

258
00:15:19,540 --> 00:15:21,980
Torej, če si jih sortirati in smo šele začeli v sredini,

259
00:15:21,980 --> 00:15:24,600
kakšna bi bila najboljša naslednja poteza bila?

260
00:15:24,600 --> 00:15:27,740
Pojdi levo. In tukaj pride na primer telefonski imenik znova.

261
00:15:27,740 --> 00:15:30,130
Če 13 je tukaj in vemo, da je seznam urejen,

262
00:15:30,130 --> 00:15:33,900
Nato vse te koščke papirja, so nezanimive za nas zdaj

263
00:15:33,900 --> 00:15:37,400
saj že vemo, da mora biti 7 na levo

264
00:15:37,400 --> 00:15:39,510
če so te številke razporejene in smo ugotovili 13.

265
00:15:39,510 --> 00:15:42,500
>> Torej, kaj je vaš naslednji korak tukaj? >> Pojdi v levo. >> Dobro, dobro.

266
00:15:42,500 --> 00:15:45,080
Torej pojdi na levo, in - počakajte, hej, hej, hej. To je goljufanje.

267
00:15:47,140 --> 00:15:51,350
Torej si našel 7, ampak kaj je algoritem sva se uporablja?

268
00:15:51,350 --> 00:15:56,450
Začnite na sredini. Dobro >>. Torej, kaj je logično nadaljevanje te iste ideje?

269
00:15:56,450 --> 00:15:58,970
Oh, samo to. >> Točno tako. >> Tako sem začel tukaj. Dobro >>.

270
00:15:58,970 --> 00:16:02,020
Torej, zdaj smo šli malo na levo znova. To je 3.

271
00:16:02,020 --> 00:16:05,310
Vendar je zanimivo takeaway zdaj Kateri vam ni treba skrbeti?

272
00:16:05,310 --> 00:16:08,040
Ti 2. Te >> 2. Torej, zdaj je to ena lahko oditi, lahko ta izgine.

273
00:16:08,040 --> 00:16:12,330
Sedaj je problem, da je bila 8 je bila velikost 4 je zdaj velikost 2.

274
00:16:12,330 --> 00:16:16,430
Dobili smo zelo blizu. Še enkrat, pojdite na sredini teh 2 elementov.

275
00:16:16,430 --> 00:16:20,430
>> Ok. Torej, to je nekako žalostno, da sedaj smo vedno tekoč zapustil, ker smo zaokroževanje navzdol.

276
00:16:20,430 --> 00:16:25,150
Ampak to je v redu, ker zdaj smo vrgli stran to in vse drugo, nam je zapustil le 7.

277
00:16:25,150 --> 00:16:30,490
Naj dajo aplavz. Našli smo 7 znova. [Aplavz] Ok. Seveda.

278
00:16:30,490 --> 00:16:32,220
Drži se za samo še 1 sekundo.

279
00:16:32,220 --> 00:16:36,630
Čeprav ta proces Naslednja vrsta je trajalo malo dlje, kot smo menili, da bi,

280
00:16:36,630 --> 00:16:40,150
odkrito povedano, vaš prvi instinkt je najboljši, kajne? Našli smo 7 trenutku.

281
00:16:40,150 --> 00:16:46,740
Vendar bi Ugotovili smo 7 hitrejši, ne glede na to, kaj je v tem primeru v primerjavi s tem 1

282
00:16:46,740 --> 00:16:50,100
ker če so številke Vse je že urejeno, tako kot strani v telefonskem imeniku,

283
00:16:50,100 --> 00:16:54,580
lahko dejansko sesekljajte polovico problema spet in spet in spet.

284
00:16:54,580 --> 00:16:56,740
In to ni čisto tako enostavno, da bi se to v samo 8 številk

285
00:16:56,740 --> 00:17:00,100
za razliko od 1.000 strani imenika, kjer ste res videli vidno,

286
00:17:00,100 --> 00:17:03,120
vendar v tem primeru, ko Sean tukaj iskal 7,

287
00:17:03,120 --> 00:17:06,020
koliko korakov v najslabšem primeru bi ga odpeljala? >> [Študent] 7.

288
00:17:06,020 --> 00:17:11,670
7 v najslabšem primeru. No, v najslabšem primeru pa 7, če obstaja 8 vrata tukaj.

289
00:17:11,670 --> 00:17:13,440
To bi mu vzeti 8 korakov.

290
00:17:13,440 --> 00:17:18,170
>> Torej, če je n vrata, je morda treba Seana pred nekaj leti n korake.

291
00:17:18,170 --> 00:17:21,520
Zdaj, v vašem primeru, Alex, glede na to, da so razporejene te številke -

292
00:17:21,520 --> 00:17:25,130
in bomo lahko te vrste sklepajo, od koder smo bili doslej v tej zgodbi -

293
00:17:25,130 --> 00:17:28,300
kaj teče čas bolj inteligenten algoritem Alex

294
00:17:28,300 --> 00:17:30,770
od začnite na sredini in nato ponavlja?

295
00:17:30,770 --> 00:17:36,490
[Študent] 3. >> Tako se dogaja, da je 3, v grobem, če greš 8-4 na 2 do 1.

296
00:17:36,490 --> 00:17:40,660
Torej, 3 korakih ali, bolj splošno, da je log n znova.

297
00:17:40,660 --> 00:17:43,380
Vsak čas si prepolovitev in prepolovitev in prepolovitev in prepolovili,

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

299
00:17:45,290 --> 00:17:48,140
In tako, da so se ti samo 3 korake in sicer je to storila

300
00:17:48,140 --> 00:17:50,890
ko smo odprli vrata prepolovitev in prepolovili,

301
00:17:50,890 --> 00:17:53,770
ker bi to bilo nekaj Sean 7 ali 8 korakov.

302
00:17:53,770 --> 00:17:56,330
Torej, hvala, ker ste z nami v tem letu. >> Hvala. Veselilo.

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

304
00:18:00,170 --> 00:18:02,150
>> Kaj pa pravi posledice tega?

305
00:18:02,150 --> 00:18:06,050
Zdaj pa si predstavljajte, da to ni 8 vrati, ki, odkrito povedano, bi vsi našli nekaj

306
00:18:06,050 --> 00:18:10,430
8 zadaj vrata zelo hitro, tako da bi raztrgal na koščke papirja in se dogaja z našimi instinkti.

307
00:18:10,430 --> 00:18:14,430
Kaj pa, če je to milijon vrata? Kaj, če je 4000000000 vrata?

308
00:18:14,430 --> 00:18:19,630
V primeru 4000000000 vrat, si zares želiš iti z algoritmom Alex,

309
00:18:19,630 --> 00:18:23,150
dvojiška iskalna kot bomo začeli kliče ali deli in vladaj, bolj na splošno,

310
00:18:23,150 --> 00:18:25,220
če boste obdržali prepolovitev in prepolovitev problem,

311
00:18:25,220 --> 00:18:30,510
ker če imate 4000000000 vrata, kolikokrat lahko sesekljamo 4000000000 na pol?

312
00:18:30,510 --> 00:18:33,870
[Študent] 32. >> Pravzaprav je 32. Delate lahko to izvajajo na papirju ali v tvoji glavi.

313
00:18:33,870 --> 00:18:38,490
Greš 4000000000-2000000000 to 1 milijardo pol milijarde evrov, na 250 milijonov evrov, pika, pika, pika.

314
00:18:38,490 --> 00:18:41,620
In če vam ven matematike, da boš res dobil 32,

315
00:18:41,620 --> 00:18:44,950
in da se dejansko nanaša na računalniške znanosti, saj smo ponavadi šteje v pristojnosti 2.

316
00:18:44,950 --> 00:18:47,600
2 do 32 se zgodi, da bo 4 milijarde EUR.

317
00:18:47,600 --> 00:18:51,440
Torej je veliko pomena za te vrste pooblastil 2 v računalništvu.

318
00:18:51,440 --> 00:18:55,120
>> Toda kaj okoli 8 milijard? Koliko korakov je, da bo trajalo, če obstajajo 8000000000 vrata?

319
00:18:55,120 --> 00:19:00,350
[Študent] 33. Torej >> 33. Kaj pa, če je 16000000000 vrata? Koliko korakov je, da bo trajalo?

320
00:19:00,350 --> 00:19:05,020
[34] študent. >> 34. Lahko bi nekako nadaljevanje tega oglasa nauseam. Ampak to je močna stvar.

321
00:19:05,020 --> 00:19:09,430
Lahko uvedejo milijarde več vhodov na vašo težavo, vendar ni nič takega,

322
00:19:09,430 --> 00:19:14,140
si vzemite 1 dodaten grižljaj od njega, zato nam kaj podobnega binarno iskanje

323
00:19:14,140 --> 00:19:15,920
ali deli in vladaj, bolj na splošno.

324
00:19:15,920 --> 00:19:17,990
Ampak jaz sem malo goljufali, kajne?

325
00:19:17,990 --> 00:19:22,410
V primeru algoritma Alex je imela prednost pred Seana.

326
00:19:22,410 --> 00:19:27,780
Vedela je, da so bile razporejene te številke, vendar pa Alex ni bilo treba razvrstiti jih sama.

327
00:19:27,780 --> 00:19:30,520
I pred prišel k tabli in vrste poskrbel

328
00:19:30,520 --> 00:19:33,670
Narisal sem, da jih vse v razvrščeni redu, potem pa sem jih prekrit s papirjem.

329
00:19:33,670 --> 00:19:35,850
Ampak koliko dela si, da me vzameš?

330
00:19:35,850 --> 00:19:40,110
Če bi se začelo s temi številkami v neki navidezno naključnem vrstnem redu -

331
00:19:40,110 --> 00:19:43,320
v tem primeru ti enostavnejši številke od 1 do 8, tu -

332
00:19:43,320 --> 00:19:46,090
kako bomo šli o razvrščanju teh vrednot?

333
00:19:46,090 --> 00:19:52,530
Če bi bili človeški saj to nalogo, kakšen pristop bi intuitivno vzameš

334
00:19:52,530 --> 00:19:54,800
sortirajo cel kup številk?

335
00:19:54,800 --> 00:19:57,050
Te stvari so bile, kot je določeno koščke. Ja.

336
00:19:57,050 --> 00:19:59,950
>> [Študent] jaz bi vsako številko in ga primerjajte z vsako od

337
00:19:59,950 --> 00:20:03,180
in nadaljuj na levi strani. >> Dobro, dobro.

338
00:20:03,180 --> 00:20:05,720
Tako se vsako številko, jo primerjati z eno poleg nje,

339
00:20:05,720 --> 00:20:09,610
in potem samo premikati po seznamu, vrste rejiggering stvari, kot si.

340
00:20:09,610 --> 00:20:13,800
Torej, tukaj imamo priložnost za morda nekaj več ljudi, da se vključijo.

341
00:20:13,800 --> 00:20:16,290
Ali imamo 8 več prostovoljcev, ki bi radi, da pridejo gor?

342
00:20:16,290 --> 00:20:23,950
Malo manj pritiska, saj nisi edini. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Pridi dol. Fantje se bodo številke od 1 do 8.

344
00:20:28,190 --> 00:20:36,050
Poglejmo, če tega ne more storiti za sortiranje Alex na zelo podoben način sem to storil vnaprej.

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

346
00:20:37,640 --> 00:20:40,760
Pojdi naprej in če bi, line up na odru med glasbeno stojalo in jaz tukaj

347
00:20:40,760 --> 00:20:44,960
v istem vrstnem redu kot diapozitiv na zaslonu.

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

349
00:20:50,370 --> 00:20:53,230
Vas bomo delati v naslednjem primeru. Oh, čakaj, čakaj. Pa gremo. Počakaj.

350
00:20:53,230 --> 00:20:57,570
Naslednji primer je zdaj. Tukaj imaš. Število 8. Pridi gor.

351
00:20:57,570 --> 00:21:00,270
V redu. Razvrsti sami v skladu s tem.

352
00:21:00,270 --> 00:21:03,620
Potisnite samo malo na stran glasbe stojim tukaj.

353
00:21:03,620 --> 00:21:12,310
Torej imamo 4, 2, 6 - noter, tukaj, tukaj - 3.

354
00:21:12,310 --> 00:21:17,570
Ja. Ok. Ti pojdi tja. Ne, ostani tam.

355
00:21:17,570 --> 00:21:21,840
Ja, prav tam. Ne motim. Prav tam. Dobro, zelo dobro. Ok.

356
00:21:21,840 --> 00:21:24,930
Torej, zdaj pa jih razvrstite v naraščajočem vrstnem redu.

357
00:21:24,930 --> 00:21:26,210
>> Kako naj grem o tem?

358
00:21:26,210 --> 00:21:28,630
Algoritem, ki je bil predlagan pred nekaj trenutki je, zakaj ne bi preprosto primerjavo

359
00:21:28,630 --> 00:21:31,970
so ljudje, ki so nekako drug poleg drugega in nato popraviti vse napake,

360
00:21:31,970 --> 00:21:33,540
premika od leve proti desni.

361
00:21:33,540 --> 00:21:36,580
Torej, tukaj imamo 4 in 2, ki je očitno v okvari. Naj te zamenjati. Ok.

362
00:21:36,580 --> 00:21:40,760
Torej, zdaj bom za premikanje po vrsti. 4 in 6, nope. [Smeh]

363
00:21:40,760 --> 00:21:45,010
6 in 8, kar dober. 8 in 1, dovolite mi, swap vas. V redu.

364
00:21:45,010 --> 00:21:48,030
Torej, 8 in 3, swap fantje.

365
00:21:48,030 --> 00:21:52,280
8 in 7, dovolite mi, swap vas. 5 in 8, odlično.

366
00:21:52,280 --> 00:21:54,820
Dam razvrščen seznam.

367
00:21:54,820 --> 00:21:56,860
V redu. Torej ne povsem.

368
00:21:56,860 --> 00:22:01,180
Vendar je bolje, ker je večji številke - primerov v točki 8 -

369
00:22:01,180 --> 00:22:04,030
so nekako vrela iz leve na desno.

370
00:22:04,030 --> 00:22:08,010
Tako sem dobil 1 izmed njih v redu, vendar je občutek ta ni povsem rešila problem.

371
00:22:08,010 --> 00:22:11,150
>> Torej, kaj bi predlagali bomo naredili sedaj? >> [Študent] Naj to počne. Še naprej >> počne.

372
00:22:11,150 --> 00:22:13,740
In spoznali, spet smo postavili stvari, ki jih le ob vse ljudi

373
00:22:13,740 --> 00:22:17,180
nekako pametno se uredijo na podlagi te slike,

374
00:22:17,180 --> 00:22:19,040
zdaj pa moramo biti veliko bolj metodično.

375
00:22:19,040 --> 00:22:21,510
Moramo biti algoritemsko o tem, kot da smo pisanje kode -

376
00:22:21,510 --> 00:22:23,520
v tem primeru besedni psevdokod.

377
00:22:23,520 --> 00:22:26,040
Zato mi dovolite, da poskusite znova. To je delal zelo dobro. Ni ga rešiti.

378
00:22:26,040 --> 00:22:30,400
Ampak, ko dvomim, samo poskusite in poskusite znova. Torej, 2 in 4, ni več pomagati.

379
00:22:30,400 --> 00:22:33,200
4 in 6. Ah! 6 in 1, kar je nekoliko bolje.

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

381
00:22:39,740 --> 00:22:44,060
In veste, sem lahko verjetno prezreti 8 sedaj, ker je na koncu seznama.

382
00:22:44,060 --> 00:22:47,250
Mogoče mi ne bo treba skrbeti nekdo mimo njega.

383
00:22:47,250 --> 00:22:49,240
Toda poglejmo, če je to varno predpostavko.

384
00:22:49,240 --> 00:22:52,340
Zdaj je seznam - prekleto - ni urejen. Poskusimo še enkrat.

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

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

387
00:22:59,230 --> 00:23:04,890
6, 7 in 8, dobro. Ampak obvestilo, sem lahko samo ustavi tukaj in zdaj ustaviti tu?

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

389
00:23:07,770 --> 00:23:11,160
Kaj pa, če je kdo od vas že številka 9 pa vse tja?

390
00:23:11,160 --> 00:23:13,640
To bi bilo urejeno. Dobro >>. To bi bilo prvič razporejene okoli.

391
00:23:13,640 --> 00:23:16,050
Dobro. Torej greva nazaj. Skoraj smo že tam.

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

393
00:23:22,800 --> 00:23:26,640
>> Zdaj sem naredil, vendar pa se mi računalnik, ki lahko samo to, kar sem rekel, da ne,

394
00:23:26,640 --> 00:23:30,120
in moj edini spomin sedaj je, da sem v bistvu le naredil nekaj dela.

395
00:23:30,120 --> 00:23:31,700
Nekaj ​​se je spremenilo tukaj.

396
00:23:31,700 --> 00:23:37,100
Torej nisem tehnično potrdili vizualno ali algoritmično, da je ta seznam dejansko razporejene.

397
00:23:37,100 --> 00:23:40,720
Torej samo za dober ukrep, tako da je analni o tem, kaj je to storiti 1 več časa.

398
00:23:40,720 --> 00:23:44,040
Torej 1 in 2, 2 in 3, 3 in 4. In veste kaj?

399
00:23:44,040 --> 00:23:46,190
Samo za dober ukrep, bom spremljate na moji roki tokrat

400
00:23:46,190 --> 00:23:51,110
koliko zamenjave sem ti samo zato, da vem, koliko dela sem dejansko naredil.

401
00:23:51,110 --> 00:23:56,930
3 in 4, 4 in 5, 5 in 6, 6 in 7, 7 in 8. Brez zamenjave.

402
00:23:56,930 --> 00:24:00,800
Torej, zdaj bi legitimno idiot, da to storijo še enkrat

403
00:24:00,800 --> 00:24:03,330
ker če sem ne dela prek tega prelaza na človeka,

404
00:24:03,330 --> 00:24:06,710
potem je jasno, da se bo to spet zgodilo, če nobena od njih je nekako naključno

405
00:24:06,710 --> 00:24:10,410
adversarially se gibljejo. Sedaj lahko neham.

406
00:24:10,410 --> 00:24:15,120
Zdaj pa vprašati, koliko dela je to dejansko me je vzel?

407
00:24:15,120 --> 00:24:18,260
Koliko korakov pa to trajalo? N >> kvadrat.

408
00:24:18,260 --> 00:24:20,400
Ja, tako n kvadrat. Kje ste dobili n kvadrat iz?

409
00:24:20,400 --> 00:24:22,660
Moraš preveriti vsako cilindrov -

410
00:24:22,660 --> 00:24:26,530
Tu je n število, in boste morali preveriti vsako številko z drugimi n številk.

411
00:24:26,530 --> 00:24:29,030
Dobro. >> Torej je n kvadrat. Dobro >>.

412
00:24:29,030 --> 00:24:31,060
>> Tako se zdi, kot bi to bilo zelo dobro n kvadrat, kajne?

413
00:24:31,060 --> 00:24:33,820
Tam je n od teh fantov, 8, posebej v tem primeru,

414
00:24:33,820 --> 00:24:37,590
ampak vsakič, ko sem šel skozi ta seznam, sem primerjavo prvo osebo, proti drugi,

415
00:24:37,590 --> 00:24:39,650
drugega proti tretji spet in spet in spet,

416
00:24:39,650 --> 00:24:42,450
in ko sem prišel do konca, kaj sem naredil? Sem ga uredil.

417
00:24:42,450 --> 00:24:46,280
Torej, če se sploh to razlago, imamo n ljudi

418
00:24:46,280 --> 00:24:51,090
in delam, seveda, 8 korakov, n korakih, vsakič, ko grem skozi ta algoritem.

419
00:24:51,090 --> 00:24:56,070
Toda koliko krat v najslabšem primeru moram iti skozi ta seznam ljudi?

420
00:24:56,070 --> 00:24:59,370
[Študent] N-krat. Verjetno >> n, prav, saj v najslabšem primeru,

421
00:24:59,370 --> 00:25:03,410
kar je verjetno najslabši primer razporeditev teh fantov od zaslužiti-go?

422
00:25:03,410 --> 00:25:06,520
Če jih popolnoma obrnil vrstni red

423
00:25:06,520 --> 00:25:09,310
Verjetno zato, ker samo mentalno, let's - Kako ti je ime? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Ok. Torej Bowen, pridi sem za trenutek.

425
00:25:12,510 --> 00:25:16,150
>> Recimo, da je Bowen je tukaj na začetku algoritma,

426
00:25:16,150 --> 00:25:19,790
in ne vem, kaj vsi ostali, ampak Bowen tukaj, glede na to algoritem -

427
00:25:19,790 --> 00:25:23,820
in če želite samo sprehod z mano - se bo do balona, ​​kot je to storil prvič okoli,

428
00:25:23,820 --> 00:25:25,740
vse do konca.

429
00:25:25,740 --> 00:25:29,400
Recimo, da je oseba, ki poleg Bowen je bila številka 7.

430
00:25:29,400 --> 00:25:33,450
Moram iti nazaj in dobil številko 7, kar pomeni, moram iti vso pot nazaj.

431
00:25:33,450 --> 00:25:36,980
Zdaj moram imeti to isto sprehod z osebo, ki je številka 7.

432
00:25:36,980 --> 00:25:40,140
Toda kaj, če pa je bila številka 6 zraven njega, pa tudi?

433
00:25:40,140 --> 00:25:42,180
Potem sem moral iti nazaj in dobil 6.

434
00:25:42,180 --> 00:25:46,490
Torej, še enkrat, na vsaki ponovitvi te zanke govorim za vsakega od n ljudi,

435
00:25:46,490 --> 00:25:50,090
in bi mi morali n teh sprehodih, da poskrbite, da sem vleče

436
00:25:50,090 --> 00:25:53,760
vsi elementi največjih nazaj in nazaj in nazaj do samega konca seznama.

437
00:25:53,760 --> 00:25:58,230
Torej n stvari n-krat je le n-krat n ali n kvadrat.

438
00:25:58,230 --> 00:26:02,050
>> Torej, tukaj že imamo algoritem, ki je ni več n, ki je ni več log n,

439
00:26:02,050 --> 00:26:04,820
je dejansko slabše kot karkoli smo že naredili prej.

440
00:26:04,820 --> 00:26:09,840
Torej, Alex nekako imam srečo, da sem naredil vse delo očitno spredaj za njo,

441
00:26:09,840 --> 00:26:14,690
vse drago delo, tako da lahko ona uživa v tem binarnega iskalnega algoritma,

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

443
00:26:16,420 --> 00:26:18,240
Ampak to je v skladu s temo v ponedeljek.

444
00:26:18,240 --> 00:26:23,260
Dali smo malo več prostora, smo uporabili več bitov, da bi pospešila svoj delovni čas.

445
00:26:23,260 --> 00:26:26,170
Toliko kot da je ta kompromis med časom in prostorom,

446
00:26:26,170 --> 00:26:31,060
obstaja tudi samo se kompromisi med porabljen čas do sprednje vrste so stvari pripravljene, da gredo

447
00:26:31,060 --> 00:26:35,000
in dejansko izvedbo algoritma, kot so iskanje. Poskusimo še enega.

448
00:26:35,000 --> 00:26:39,050
Če vidva ne bi motilo, samo hitro preurejanjem sami, da bi ustrezala ponovno

449
00:26:39,050 --> 00:26:42,240
poskusimo nekaj malce drugačen, če to ni tako preprosto

450
00:26:42,240 --> 00:26:45,760
kot le popraviti vse napake, parno, ki je zelo intuitiven.

451
00:26:45,760 --> 00:26:48,150
Naj se namesto tega malo bolj premišljeno in to.

452
00:26:48,150 --> 00:26:51,010
Ta Tudi jaz bi predlagal, je verjetno precej intuitivna.

453
00:26:51,010 --> 00:26:55,070
>> Naj izberite najmanjšo osebo s seznama znova in znova. Torej, gremo.

454
00:26:55,070 --> 00:26:57,350
4, ste najmanjša oseba, ki sem torej videl doslej,

455
00:26:57,350 --> 00:27:00,520
Tako bom duševno zapomniti, da jih samo kaže na vas za zdaj.

456
00:27:00,520 --> 00:27:05,020
2. Oh! Pozabite številko 4. Pravkar sem ugotovila, da je nov najmanjši element na tem seznamu.

457
00:27:05,020 --> 00:27:07,410
Grem na vrsto zapomniti. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Oh! 1. Nasvidenje. Torej, zdaj bom zapomniti številko 1.

459
00:27:11,190 --> 00:27:14,790
Vemo, da 1 je najmanjši, ampak sem računalnik. Kaj pa, če je 0?

460
00:27:14,790 --> 00:27:17,140
Kaj pa, če je -1? Moram naprej.

461
00:27:17,140 --> 00:27:20,990
Torej, 3, 7, 5, nope. Ok. Torej, številka 1 je najmanjša.

462
00:27:20,990 --> 00:27:23,640
Naj vas izberite iz seznama - Bomo iti po tej poti -

463
00:27:23,640 --> 00:27:27,760
in si dal samovoljno na začetku seznama.

464
00:27:27,760 --> 00:27:29,740
Počakaj malo. Nekako sem goljufal.

465
00:27:29,740 --> 00:27:34,010
Če ti fantje sestavljati seznam 8 oseb, ampak z matriko,

466
00:27:34,010 --> 00:27:37,050
8 kosi strnjenega pomnilnika - Imate kaj proti korak nazaj za trenutek?

467
00:27:37,050 --> 00:27:39,060
Tam je dejansko ni prostora za vas tukaj.

468
00:27:39,060 --> 00:27:41,840
Torej, kako bomo naredili prostor - Kako ti je ime? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kako naredimo prostor za Sammyja?

470
00:27:43,710 --> 00:27:46,760
>> Gremo na n, ki so pred mano. >> Redu.

471
00:27:46,760 --> 00:27:48,850
Tako smo lahko premikate n ljudi, ki so pred njim,

472
00:27:48,850 --> 00:27:52,400
tako da, če vi želite, da 1 namerno, dramatičen korak v levo.

473
00:27:52,400 --> 00:27:57,000
Vsi so naredili, da je v sozvočju, ampak nazadnje, ko sem napisal nekaj kode,

474
00:27:57,000 --> 00:27:59,740
ne moreš nekako premakniti veliko stvari naenkrat.

475
00:27:59,740 --> 00:28:02,450
Lahko bi to naredil v zanko, ki se gibljejo vse enkrat naenkrat.

476
00:28:02,450 --> 00:28:04,340
Torej, če vi ne bi motilo, korak nazaj na desno,

477
00:28:04,340 --> 00:28:07,230
in Sammy, če bi lahko korak nazaj, saj je še vedno ni prostora za vas,

478
00:28:07,230 --> 00:28:11,420
zdaj pa to. Kje je Sammy pred nekaj trenutki? Prav tam.

479
00:28:11,420 --> 00:28:16,140
Torej je razlika obstaja. Torej si lahko premaknete v mestu Sammy.

480
00:28:16,140 --> 00:28:20,580
Zdaj naslednja oseba in zdaj naslednjo osebo, ki je zdaj naslednja oseba. Zdaj imamo prostor za Sammyja.

481
00:28:20,580 --> 00:28:23,490
Sedaj, nekdo iz občinstva - to je bilo dobro, da je bila pravilna,

482
00:28:23,490 --> 00:28:27,070
se mu je zdelo malo časa - kaj hitreje? Ja.

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

484
00:28:29,440 --> 00:28:33,200
>> Torej, v skladu s to temo le s kompromisi, zakaj ne bi sem narediti nov niz

485
00:28:33,200 --> 00:28:36,570
 in potem bo Sammy je kopanje v prostoru pred temi ljudmi, na primer,

486
00:28:36,570 --> 00:28:39,600
in bomo lahko šele začetek polnjenja nov niz v celoti. To bi bilo preveč dela.

487
00:28:39,600 --> 00:28:42,450
Ampak me ne zanima porabi več prostora danes. Kaj je drugačen pristop?

488
00:28:42,450 --> 00:28:46,630
[Študent] menjavo. >> Redu. Lahko bi samo zamenjali teh 2 guys. Kako ti je ime?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Torej Mario, da si zdaj tu.

490
00:28:49,390 --> 00:28:52,480
Sammy, lahko nazaj gor za trenutek? Mario je bil tukaj.

491
00:28:52,480 --> 00:28:55,830
Nimamo prostora za tabo, tako da če ne bi imel nič proti, če bo Sammy je,

492
00:28:55,830 --> 00:29:02,430
bomo napisali Sammy tukaj in zdaj bi lahko dejali, da je bila menjava delovanje Sammy je veliko hitreje.

493
00:29:02,430 --> 00:29:06,370
To smo storili, da bi zamenjali 1 delovanje te ljudi, ali pa 2, da bi zamenjali te fante,

494
00:29:06,370 --> 00:29:11,210
vendar nismo naredili 1, 2, 3, 4, tako da se počuti bolje. Počakaj malo.

495
00:29:11,210 --> 00:29:14,660
Nekako je problem slabše, ker številka 4 je nekako blizu začetka.

496
00:29:14,660 --> 00:29:19,470
Sedaj številka 4 je malo bližje, da v ta namen, vendar nisem vedela, ali zanima.

497
00:29:19,470 --> 00:29:23,330
Torej, to je samo slaba sreča, da je številka 4 je malce dlje od svojega namenjeno mesto.

498
00:29:23,330 --> 00:29:25,110
Torej, kaj je zdaj to ponovi algoritem.

499
00:29:25,110 --> 00:29:28,410
>> Če povzamem, dokler ta zgodba je bila vse, kar si je sprehod skozi seznam

500
00:29:28,410 --> 00:29:31,130
išče najmanjše oštevilčeno osebe.

501
00:29:31,130 --> 00:29:34,530
Torej, zdaj gremo še enkrat. Mi ne bo treba skrbeti, Sammy več.

502
00:29:34,530 --> 00:29:37,590
Lahko samo pojdi tukaj. Oh! Številka 2. To je zelo majhno število.

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
In na srečo, naključje, mi ni treba premakniti - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie, ker je v svojem pravem mestu zdaj.

506
00:29:45,910 --> 00:29:48,110
Naredimo to še enkrat in prezreti teh 2 guys.

507
00:29:48,110 --> 00:29:50,460
6. To je zelo majhno število. Oh! 8 je zagotovo večja.

508
00:29:50,460 --> 00:29:53,410
4. Osredotočimo se na 4. Oh! 3 je še boljši.

509
00:29:53,410 --> 00:29:58,290
7 in 5. Torej, kaj bova zdaj s - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Naj ga zamenjali s številko 6.

511
00:30:00,250 --> 00:30:03,570
Torej, če 6 in 3 bi radi zamenjali,

512
00:30:03,570 --> 00:30:07,320
smo zdaj nekako prišel srečen v tem 6 je bližje, če bi bila tam,

513
00:30:07,320 --> 00:30:10,300
ampak to je samo naključje tukaj. Torej, kaj je zdaj kliknite tukaj.

514
00:30:10,300 --> 00:30:13,430
8 je zelo majhno število. Oh! 4 je manjša.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Kaj bomo pa zdaj? >> Menjavo. >> Točno tako.

516
00:30:17,130 --> 00:30:19,010
Torej, zdaj naredimo to vrsto hitreje.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Kje 5 iti? Dobro. Ok.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 dobi, da ostanejo tam, kjer je. Kako ti je ime? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie dobi prenočiti, kje je. 7 gets - Pa poglejmo. 7, 8. Ok.

520
00:30:31,770 --> 00:30:35,100
Torej 7 postane prenočiti, kje je. Kako ti je ime? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Torej Amna dobi prenočiti, kje je, in številka 8 je že, če bi moral biti zdaj.

522
00:30:39,670 --> 00:30:43,960
Dobro, dobro. Počutim se, kot da smo samo ustvariti delo za nas tukaj, čeprav.

523
00:30:43,960 --> 00:30:47,440
Kaj je končno čas delovanja tega algoritma?

524
00:30:47,440 --> 00:30:51,900
Če mislimo, da o teh ljudeh ne kot 8, vendar kot n? >> To je n.

525
00:30:51,900 --> 00:30:55,440
To je n ukrepe, vendar smo kontrolo vsak čas.

526
00:30:55,440 --> 00:30:57,570
Ok. N a ste preverjanje vsak čas?

527
00:30:57,570 --> 00:31:03,450
V redu, če pa je n ukrepe, ne bi mi bilo, da vas lahko razvrstite po pravkar dogaja 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
Torej n kvadrat, zakaj? Kaj se v resnici dogaja?

530
00:31:08,050 --> 00:31:12,130
Tukaj je n ljudi na tem seznamu, vendar da bi našli najmanjšo osebo na seznamu

531
00:31:12,130 --> 00:31:16,200
V najslabšem primeru, koliko korakov moram sprejeti? N. >>

532
00:31:16,200 --> 00:31:19,160
>> N, prav, saj v najslabšem primeru, številka 1 je vso pot tja,

533
00:31:19,160 --> 00:31:20,990
tako da sem moral iti ponj ali ona.

534
00:31:20,990 --> 00:31:25,500
In potem, ko sem končno spoznali 1 je bil najmanjši, potem je zelo hitro, da jih swap.

535
00:31:25,500 --> 00:31:28,450
Ampak zdaj moram začeti od začetka in si za koga?

536
00:31:28,450 --> 00:31:31,980
Naslednji Najmanjše oseba, ki je 2. Če je v najslabšem primeru znaša 2?

537
00:31:31,980 --> 00:31:34,320
Oh, moj bog. To je vse tako sem na koncu.

538
00:31:34,320 --> 00:31:37,000
Torej, zdaj sem pravkar naredil še n korake, še n korakih.

539
00:31:37,000 --> 00:31:41,200
In če imamo n ljudi in v najslabšem primeru najmanjša oseba n korakov,

540
00:31:41,200 --> 00:31:45,230
To je še n-krat n, in tako smo spet bili n kvadrat.

541
00:31:45,230 --> 00:31:47,280
To se ne počuti dobro.

542
00:31:47,280 --> 00:31:52,150
In v resnici, tudi v najboljšem primeru - Predvidevam, da začnete razporejene -

543
00:31:52,150 --> 00:31:59,080
koliko korakov je potrebnih, da sem z uporabo tega algoritem za razvrščanje teh n ljudi?

544
00:31:59,080 --> 00:32:01,010
N kvadrat. >> Slišal sem n kvadrat. Zakaj n kvadrat?

545
00:32:01,010 --> 00:32:05,240
Ker imate še vedno preveriti vsak čas. >> Ja.

546
00:32:05,240 --> 00:32:08,060
In jih morate zamenjati. >> Čeprav smo ljudje nekako vsemogočni

547
00:32:08,060 --> 00:32:10,770
v smislu, vizualno, da bomo lahko kar nekako vidim, da je urejen tako,

548
00:32:10,770 --> 00:32:12,140
Računalnik ni tako pameten.

549
00:32:12,140 --> 00:32:14,040
To se dogaja, da si tukaj in tukaj in tukaj,

550
00:32:14,040 --> 00:32:16,610
če pa kaj je iskal je najmanjši element,

551
00:32:16,610 --> 00:32:22,110
ste samo vem, da ste našli najmanjši element, do katerega bistvo? Ko ste na koncu.

552
00:32:22,110 --> 00:32:25,880
Toda na tej točki ste našli le trenutno najmanjši element.

553
00:32:25,880 --> 00:32:28,810
Saj ni nujno, veš kaj o stanju sveta.

554
00:32:28,810 --> 00:32:30,880
Torej boste morali spet in spet in spet.

555
00:32:30,880 --> 00:32:34,880
>> Torej, tokrat sem res videti neumno, ker sem kontrolo, ok, 2, si je najmanjša,

556
00:32:34,880 --> 00:32:37,530
ampak jaz ne vem, da v celoti še ni.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Dobro, dobro. 2 je res najmanjši.

558
00:32:41,090 --> 00:32:43,150
Zdaj pa je bil naslednji najmanjši. Ok.

559
00:32:43,150 --> 00:32:48,350
3, ste trenutno najmanjši. Pa poglejmo. 4, 5, 6, 7, 8. Ok, imaš srečo še enkrat.

560
00:32:48,350 --> 00:32:53,170
3 je bil res na pravem mestu. Vendar bom vztrajati početje to znova in znova in znova.

561
00:32:53,170 --> 00:32:55,990
Kako lahko to storimo vedno tako malo bolje?

562
00:32:55,990 --> 00:33:00,120
Namesto da bi ljudje mehurček gor Pairwise od najmanjšega do največjega

563
00:33:00,120 --> 00:33:04,350
in namesto da bi šel naprej in nazaj po seznamu izberete ta pa najmanjši osebo,

564
00:33:04,350 --> 00:33:09,780
Zakaj ne bi namesto vstaviti te ljudi v nov korak za korakom seznama?

565
00:33:09,780 --> 00:33:13,080
Poskusimo tole. Zdaj pa me poklical te vrste stvar vstavljanja.

566
00:33:13,080 --> 00:33:17,250
Torej, tukaj smo tukaj. Številka 1. Ne skrbi nikomur na tem seznamu.

567
00:33:17,250 --> 00:33:21,310
Moj cilj sedaj je, da se številka 1 na začetku razvrščeni seznama.

568
00:33:21,310 --> 00:33:23,910
In jaz bom predlagala, ker imam samo 8 kose pomnilnika,

569
00:33:23,910 --> 00:33:28,670
samovoljno zdaj sem zid med mojimi naj nesortiranih seznamu

570
00:33:28,670 --> 00:33:32,740
in je razvrščen vsakdo, ki je za sabo bom trdijo.

571
00:33:32,740 --> 00:33:34,680
Torej, zdaj imamo številko 1.

572
00:33:34,680 --> 00:33:39,240
Želim, da ga vstavite v mojem razvrščenih seznam, tako da bom samo, da se premaknete svoj zid tukaj,

573
00:33:39,240 --> 00:33:43,930
zdaj pa trdijo, ta seznam je urejen, je ta seznam nerazvrščeno - vsaj kolikor jaz vem.

574
00:33:43,930 --> 00:33:46,070
Ne vidim vse številke naenkrat.

575
00:33:46,070 --> 00:33:49,000
>> Zdaj sem se zgodi, da naletijo na številne 2. Kaj naj naredim z njim?

576
00:33:49,000 --> 00:33:54,380
Sem ti vstavite zdaj na seznamu razvrščeni. Toda opazil, kako enostavno je to.

577
00:33:54,380 --> 00:33:59,650
Sem moral pogledati. Številka 1 je tam. Oh, seveda 2 gre na strani številka 1.

578
00:33:59,650 --> 00:34:03,700
No, kaj naj naredim s 3? Sem ti vstavite v seznamu razvrščeni. Ampak to je bilo super enostavno.

579
00:34:03,700 --> 00:34:07,250
To je super enostavno, je to super lahka, to je super enostavno, super enostavno, super enostavno.

580
00:34:07,250 --> 00:34:12,790
In zdaj je vse razporejene za mano, in koliko korakov se je to trajalo?

581
00:34:12,790 --> 00:34:15,620
[Študenti] >> N. Torej je le n. Imeli smo srečo.

582
00:34:15,620 --> 00:34:18,860
Bilo je le n zakaj? >> [Študent] Ker je bil razvrščen seznam.

583
00:34:18,860 --> 00:34:21,630
Seznam je že urejeno. Torej imamo srečo.

584
00:34:21,630 --> 00:34:25,639
Ampak smo zasnovali algoritem, ki ta čas, da ramenskimi toliko sreče,

585
00:34:25,639 --> 00:34:29,420
da je najboljši scenarij, ki ga ne bi izgubljali časa po nepotrebnem.

586
00:34:29,420 --> 00:34:31,750
Tako imamo zdaj, kaj bomo poklicali mehurček vrste

587
00:34:31,750 --> 00:34:33,949
kjer se ljudje nekako balona do parne.

588
00:34:33,949 --> 00:34:38,100
Zdaj imamo izbiro vrste, kjer smo Istrgnuti najmanjšo osebo, znova in znova.

589
00:34:38,100 --> 00:34:42,350
In zdaj imamo nekakšno vstavljanja, kjer smo nekako proaktivno, da ljudi, kamor sodijo

590
00:34:42,350 --> 00:34:45,000
v vse bolj razvrščenih seznama.

591
00:34:45,000 --> 00:34:49,679
Če bi lahko, aplavz za te fante tukaj. [Aplavz]

592
00:34:49,679 --> 00:34:52,310
Vzemimo našo 5-minutni odmor tukaj.

593
00:34:52,310 --> 00:34:55,139
In ko se vrnemo, bomo razstrelili vse te algoritmov iz vode

594
00:34:55,139 --> 00:35:00,260
nekaj boljšega. V redu. Najlepša hvala. Lahko da so kot spominke.

595
00:35:01,710 --> 00:35:04,330
V redu. Mi smo nazaj.

596
00:35:04,330 --> 00:35:08,420
>> In če povzamem zelo hitro, smo te 3 različne pristope za sortiranje,

597
00:35:08,420 --> 00:35:13,000
bistvo, ki naj bi prišli do točke, ko nekdo kot Alex

598
00:35:13,000 --> 00:35:16,930
lahko poiščete seznam številk hitreje kot nekoga, kot je Sean lahko.

599
00:35:16,930 --> 00:35:19,830
In čeprav imamo tako preproste primere z 8 številk,

600
00:35:19,830 --> 00:35:24,000
bi lahko ekstrapolirajo z lahkoto do 8 spletnih strani, 8 milijard spletnih strani,

601
00:35:24,000 --> 00:35:26,680
ali 800000000 prijatelji na Facebooku.

602
00:35:26,680 --> 00:35:30,090
Tako lahko ti algoritmi zagotovo lestvico za tiste vrste vrednosti,

603
00:35:30,090 --> 00:35:32,300
in ideje so na koncu isti.

604
00:35:32,300 --> 00:35:36,140
Tako nekako mehurček je bil prvi, kjer smo nekako vrela največji osebo

605
00:35:36,140 --> 00:35:39,110
vse do pravice z zamenjavo ljudi Pairwise.

606
00:35:39,110 --> 00:35:42,040
Potem smo imeli kaj bomo poklicali izbiro vrste, kjer sem malo bolj premišljeno

607
00:35:42,040 --> 00:35:46,480
hranijo išče po seznamu, izberite najmanjše število znova in znova in znova,

608
00:35:46,480 --> 00:35:49,530
logična posledica je, da je seznam na koncu razvrščeni.

609
00:35:49,530 --> 00:35:53,780
Potem pa v tretjo, sem vstavil ljudi v njihovem ustreznem mestu

610
00:35:53,780 --> 00:35:57,720
in smo zelo izmišljene primer v tem, da je bil seznam že urejen,

611
00:35:57,720 --> 00:36:01,100
ampak to je bilo, da pošljete sporočilo, da je v primeru vstavljanja sortiraj je,

612
00:36:01,100 --> 00:36:02,670
lahko posreči.

613
00:36:02,670 --> 00:36:07,930
Če so številke že razporejene, to je samo še, da vas n korakov za potrditev toliko,

614
00:36:07,930 --> 00:36:10,870
ker neke izbire, da si malo bolj predor vizijo

615
00:36:10,870 --> 00:36:14,360
in ti nikoli ne zavedaš, da je ta seznam že urejeno.

616
00:36:14,360 --> 00:36:16,830
Torej, da vidimo neke mehurčke v akciji tukaj.

617
00:36:16,830 --> 00:36:19,590
V tem primeru, bomo kmalu videli navpične črte

618
00:36:19,590 --> 00:36:23,030
katerih višina predstavljajo številk, tako da bomo lahko nekako vizualiziramo sortiranje zgodilo.

619
00:36:23,030 --> 00:36:26,630
Manjša kot je bar, tem manjše je število, večja kot je bar, večja številka.

620
00:36:26,630 --> 00:36:28,860
>> In ga bomo igrali na tej privzeti hitrosti.

621
00:36:28,860 --> 00:36:33,460
To se dogaja, da se premaknete malo hitro za zdaj, vendar je rdeča, kaj se kaže tudi 2 bara

622
00:36:33,460 --> 00:36:35,480
se v primerjavi drug ob drugem.

623
00:36:35,480 --> 00:36:39,520
In če gledate pozorno, kaj se zgodi, je, da če so palice v okvari,

624
00:36:39,520 --> 00:36:42,300
se manjši gets preselila na levo, širšo 1 na desni,

625
00:36:42,300 --> 00:36:44,360
in potem naprej napreduje.

626
00:36:44,360 --> 00:36:48,520
Torej, če to počnemo znova in znova, da vidite, da je najmanjša palice

627
00:36:48,520 --> 00:36:51,090
se dogaja, da inching svojo pot na levo

628
00:36:51,090 --> 00:36:54,130
in največji palice dogaja, da inching svojo pot na desni.

629
00:36:54,130 --> 00:36:58,490
In res, smo začeli videti vzorcu, vso pot na desni strani

630
00:36:58,490 --> 00:37:04,790
tako kot smo videli, 8 in nato sčasoma 7 vpihavanjem do skrajnem koncu našega seznama ljudi.

631
00:37:04,790 --> 00:37:08,750
Torej, to se dogaja zelo hitro dobili malo dolgočasno, zato naj ustavi za trenutek.

632
00:37:08,750 --> 00:37:10,980
Naj spremembo hitrosti, da se veliko hitreje.

633
00:37:10,980 --> 00:37:15,380
Jaz ne spreminja algoritem, jaz sem samo izdelavo animacije zgodi hitreje.

634
00:37:15,380 --> 00:37:18,410
Še vedno bubble sort, enak algoritem,

635
00:37:18,410 --> 00:37:21,910
zdaj pa si lahko ogledate veliko hitreje kot naši ustno predstavitev

636
00:37:21,910 --> 00:37:25,900
da se največje elementi so dejansko vpihavanjem do vrha.

637
00:37:25,900 --> 00:37:29,860
>> Naj omenim, da so ti mali kvadratki na spodnjem levem in desnem spodnjem

638
00:37:29,860 --> 00:37:33,520
je le malo opomnike o tem, koliko primerjave delate.

639
00:37:33,520 --> 00:37:37,620
Ampak za zdaj, bomo lahko osredotočili na piramido, ki je dobiva obliko, in tam gre.

640
00:37:37,620 --> 00:37:41,510
Najmanjši element je na levi, največji na desni, in vse ostalo vmes.

641
00:37:41,510 --> 00:37:44,470
Zdaj pa namesto tega si oglejte vrste selekcijo.

642
00:37:44,470 --> 00:37:47,260
Grem, da gredo naprej in zadeti Stop. Bomo dobili nov naključni komplet palic.

643
00:37:47,260 --> 00:37:50,930
Izbor vrste, odpoklic, gre skozi seznam spet in spet in spet,

644
00:37:50,930 --> 00:37:54,900
skubljenje od najmanjšega elementa. Torej, tukaj je izbor sort.

645
00:37:54,900 --> 00:37:58,390
Videti je, da je manj dela, se dogaja zdaj, ker ne bomo primerjali parne

646
00:37:58,390 --> 00:38:02,590
vendar smo nekako cherry picking najmanjše elemente iz desne na levo.

647
00:38:02,590 --> 00:38:06,890
To je zelo malo časa, tako da je že dihotomija.

648
00:38:06,890 --> 00:38:11,820
Samo zato, ker algoritem je dejal, da n kvadrat časa, kot so vrsta mehurček

649
00:38:11,820 --> 00:38:16,100
in kot neke izbire tistih, ki so res najslabši teče čas.

650
00:38:16,100 --> 00:38:21,790
Na primer, v primeru, recimo, izbira vrste,

651
00:38:21,790 --> 00:38:27,240
Pravzaprav sem izberete najmanjšo osebo in dajanje mu tukaj

652
00:38:27,240 --> 00:38:29,620
potem to počnem še enkrat, potem pa to počnem še enkrat,

653
00:38:29,620 --> 00:38:32,070
vendar pa je prišlo do manjšega optimizacija Jaz bi lahko.

654
00:38:32,070 --> 00:38:35,040
>> Takoj, ko sem se preselil sem številka 1 - Sammy v tem primeru -

655
00:38:35,040 --> 00:38:38,630
Kaj pa moram storiti z njim potem? >> [Študent] Pustite ga.

656
00:38:38,630 --> 00:38:40,140
Pusti ga, kajne? Nič.

657
00:38:40,140 --> 00:38:44,310
Nisem je treba vedno govoriti Sammy še enkrat, ker če sem izbral najmanjši element

658
00:38:44,310 --> 00:38:48,580
in ga postavil tu, zakaj bi izgubljal čas bo konec mojega celotnega seznama?

659
00:38:48,580 --> 00:38:54,590
Na naslednji iteraciji mi dejansko premakniti samo za številko 2, samo številko 3.

660
00:38:54,590 --> 00:38:57,640
Torej, v resnici pa sem bil ne delam stvari, n n-krat.

661
00:38:57,640 --> 00:39:05,380
Opravljal sem n stvari, potem je n - 1 stvari, potem n - 2 stvari, potem n - 3 stvari,

662
00:39:05,380 --> 00:39:07,080
potem n - 4, pika, pika, pika.

663
00:39:07,080 --> 00:39:09,470
Imamo malo geometrijskem zaporedju, ki samo pomeni,

664
00:39:09,470 --> 00:39:11,450
dodajate postopoma do manjših številk.

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

666
00:39:17,940 --> 00:39:21,380
In kaj, da na splošno deluje se je, da -

667
00:39:21,380 --> 00:39:24,280
Grem pokvariti mojega sveta sem za trenutek -

668
00:39:24,280 --> 00:39:28,990
da se bo izšlo, da bi bilo kaj takega n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
če smo le nekakšen pogled na zadnji matematični knjigi, kjer imate vse Goljufaš listi

670
00:39:31,930 --> 00:39:33,410
Za formul.

671
00:39:33,410 --> 00:39:37,760
Če ste pravkar dodal nekaj n + n - 1 + n - 2, to tovarna jasno, da je nekaj takega.

672
00:39:37,760 --> 00:39:42,320
In če smo le nekako množijo iz tega, da je n kvadrat minus n / 2.

673
00:39:42,320 --> 00:39:46,400
Obdržal sem rekel n kvadrat, čeprav, in da je zato, ker sem bil nekako ob mentalno bližnjico

674
00:39:46,400 --> 00:39:51,950
ker v resnici, n kvadrat minus n deljeno z 2 je dejansko res, število korakov

675
00:39:51,950 --> 00:39:55,510
da algoritem kot neke izbire da če res šteje navzgor

676
00:39:55,510 --> 00:39:58,800
vse te primerjave, in vse malo zaseden delu smo bili početje.

677
00:39:58,800 --> 00:40:03,210
Ampak odkrito povedano, ko n dobi biti kot milijon ali milijarde, ki skrbi za vraga

678
00:40:03,210 --> 00:40:07,160
če delaš milijardo kvadrat minus milijard deljeno s 2?

679
00:40:07,160 --> 00:40:09,320
Milijarde kvadrat je ogromna številka.

680
00:40:09,320 --> 00:40:13,580
Lahko še eno milijardo off to z - n. To ni nič takega.

681
00:40:13,580 --> 00:40:18,770
Torej večji številke dobijo, manj pomembni so ti pogoji so nižje naročiti.

682
00:40:18,770 --> 00:40:24,230
Koga briga, če delimo z 2, če govorimo o quadrillions števila korakov?

683
00:40:24,230 --> 00:40:29,710
>> Torej na splošno, računalniški znanstveniki pogosto mečejo vse, ampak največji izraz,

684
00:40:29,710 --> 00:40:33,140
in smo kar nekako poenostaviti svet in rekel, da algoritem

685
00:40:33,140 --> 00:40:38,130
je približno n kvadrat korake. To je čas vožnje od algoritma.

686
00:40:38,130 --> 00:40:40,760
Torej bomo prišli nazaj na to čez nekaj trenutkov z nekaterimi konkretnimi primeri,

687
00:40:40,760 --> 00:40:45,940
vendar za zdaj, to je nekako intuitivno motivacije za tako poenostavlja naš svet

688
00:40:45,940 --> 00:40:51,170
in govori o najpomembnejših izrazov, ne pa dobili v vseh teh fancy formul.

689
00:40:51,170 --> 00:40:53,540
Tako, da je bil izbor sort in imamo malo sreče tam.

690
00:40:53,540 --> 00:40:57,360
Oglejmo si uredi po vstavitvi. Naj gredo naprej in začnemo 1, kot tudi.

691
00:40:57,360 --> 00:41:00,330
Zdaj opazite vzorec, ki se dogaja, je malo drugačna,

692
00:41:00,330 --> 00:41:03,410
in smo začeli s naključnih števil,

693
00:41:03,410 --> 00:41:06,890
če pa smo dejansko prešteti število korakov, v najslabšem primeru,

694
00:41:06,890 --> 00:41:11,070
Če je seznam začel povsem v pravem vrstnem redu,

695
00:41:11,070 --> 00:41:13,380
želimo le n ukrepe za uresničitev toliko.

696
00:41:13,380 --> 00:41:18,240
>> Ampak, če so bili dejansko nazaj seznam - na primer, v tem primeru -

697
00:41:18,240 --> 00:41:23,860
potem opazil, smo dejansko narediti veliko več dela v tej zadevi.

698
00:41:23,860 --> 00:41:27,080
Prav tako bi moral nekako občutek, da vam je všeč tale je malo težje delo

699
00:41:27,080 --> 00:41:30,900
, da bi dobili tiste manjše elemente na levi, in da je zato, ker smo dobili nesrečen.

700
00:41:30,900 --> 00:41:34,210
Seznam je bil pomotoma razvrščeni v obratnem vrstnem redu.

701
00:41:34,210 --> 00:41:38,110
V nasprotju z neke vstavljanja, če posnema, kar smo naredili z našimi ljudmi tukaj

702
00:41:38,110 --> 00:41:42,670
da se začne s razvrščene vse in nato začne, to je zelo dober algoritem, kajne?

703
00:41:42,670 --> 00:41:45,010
To je že v bistvu urejeno.

704
00:41:45,010 --> 00:41:48,670
Torej, kaj je poskušal povzeti, koliko časa te stvari jemljejo nam

705
00:41:48,670 --> 00:41:52,360
z uvedbo le nekaj žargona ali notacijo, ki je dejansko veliko enostavnejši

706
00:41:52,360 --> 00:41:54,320
kot fanciness nekako kaže.

707
00:41:54,320 --> 00:41:59,030
Ta stvar tukaj, ta velik O na zaslonu, kaj se bo računalniški znanstvenik splošno uporabo

708
00:41:59,030 --> 00:42:03,640
opisati najhujšo teče sodni čas algoritma.

709
00:42:03,640 --> 00:42:07,360
>> Še enkrat, po najslabšem primeru, to je popolnoma odvisno od konteksta.

710
00:42:07,360 --> 00:42:10,890
Kaj mislimo s najslabšem primeru popolnoma razlikuje glede na problem, govorimo o tem.

711
00:42:10,890 --> 00:42:14,550
Toda v primeru, sortiranja, kar je najslabši možen scenarij?

712
00:42:14,550 --> 00:42:17,860
Vse je nazaj, ker je samo občutek, kot da pomeni veliko dela za nas.

713
00:42:17,860 --> 00:42:21,330
Sem jotted dol nekaj algoritmov, ki smo jih videli doslej:

714
00:42:21,330 --> 00:42:24,930
linearno iskanje, binarno iskanje kot pri telefonskem imeniku ali koščke papirja,

715
00:42:24,930 --> 00:42:28,960
potem nekako bubble sort, izbira sort, in vključitev, kot smo lahko videli pri naših ljudeh,

716
00:42:28,960 --> 00:42:31,770
in nato še 1, ki je na koncu bo, da se imenuje zlivanjem.

717
00:42:31,770 --> 00:42:37,710
Torej, v linearnem iskanje v najslabšem primeru, koliko korakov je potrebnih, da bi našli številko 7

718
00:42:37,710 --> 00:42:40,690
če je n vrata, s katerimi se srečujejo, kot so Sean? >> [Študent] N.

719
00:42:40,690 --> 00:42:44,180
N. Torej bomo napisali veliko Õ n.

720
00:42:44,180 --> 00:42:47,010
Grem, da izpolnite v nekaterih prazne. To je le mreža presledki.

721
00:42:47,010 --> 00:42:52,990
Toda v najboljšem primeru z linearnim iskanju lahko, 7 je bilo na samem začetku seznama,

722
00:42:52,990 --> 00:42:55,520
in bi lahko Sean začeli iskati na začetku seznama.

723
00:42:55,520 --> 00:42:58,940
Torej, če ste z uporabo linearne iskanje in samo preverjanje leve proti desni ali pa od desne proti levi -

724
00:42:58,940 --> 00:43:02,650
oni so enakovredne - v najboljšem primeru koliko korakov bi lahko linearno iskanje,

725
00:43:02,650 --> 00:43:05,550
kot algoritem Sean je, da? Samo 1 korak.

726
00:43:05,550 --> 00:43:09,450
>> Tako bom rekel, da je omega zapis.

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

728
00:43:11,570 --> 00:43:15,000
Omega je le seksi način rekel najboljšem primeru teče čas.

729
00:43:15,000 --> 00:43:18,900
Torej v najboljšem primeru teče čas je sam korak ali stalno število korakov -

730
00:43:18,900 --> 00:43:24,270
1 v tem primeru - ampak v najslabšem primeru, veliki O, je dejansko n korakov.

731
00:43:24,270 --> 00:43:28,110
In tale tukaj, theta, mi pravzaprav ne gre iskati v tem trenutku.

732
00:43:28,110 --> 00:43:30,090
To ni pomembno za to posebno primer.

733
00:43:30,090 --> 00:43:31,990
Ampak zdaj poskusiva binarno iskanje.

734
00:43:31,990 --> 00:43:35,990
V najslabšem primeru z binarno iskanje, koliko korakov je bo trajalo, da bi našli številko 7

735
00:43:35,990 --> 00:43:38,340
ali karkoli že iščemo? >> [Študent] Prijavi n.

736
00:43:38,340 --> 00:43:40,980
Še vedno se dogaja, da se log n, ker tako kot Alex dobil sreče

737
00:43:40,980 --> 00:43:44,030
ko smo res delali skozi problem metodično

738
00:43:44,030 --> 00:43:48,220
in ona ni našel številko 7 do zadnjega vratih je gledala,

739
00:43:48,220 --> 00:43:51,720
čeprav je v pravičnosti, je prišla do mečejo nekatere vrata na tej poti,

740
00:43:51,720 --> 00:43:56,920
binarno iskanje v najslabšem primeru ima zaporedno čas log n.

741
00:43:56,920 --> 00:43:59,230
In še enkrat, da se govori, da je to tako in osvajanje.

742
00:43:59,230 --> 00:44:01,140
Toda kaj je v najboljšem primeru?

743
00:44:01,140 --> 00:44:04,790
In Alex je dejansko prišlo, da je najboljši primer prav, ko je prišla na oder.

744
00:44:04,790 --> 00:44:07,290
Koliko korakov, da bi si v binarnem iskanju? >> [Študent] 1.

745
00:44:07,290 --> 00:44:09,380
1, samo zato, ker je dobila srečo.

746
00:44:09,380 --> 00:44:12,520
Ampak to je v redu, ker se nanaša na omega najboljših scenarijev,

747
00:44:12,520 --> 00:44:15,770
Najboljši vnosi primeru, tudi če je samo naključna sreča.

748
00:44:15,770 --> 00:44:18,900
>> No, tudi to bomo le nekakšno slepo dopusta za zdaj.

749
00:44:18,900 --> 00:44:21,010
Kaj pa zdaj bubble sort?

750
00:44:21,010 --> 00:44:24,290
V najslabšem primeru z neke mehurčkov, vsi so v obratnem vrstnem redu,

751
00:44:24,290 --> 00:44:26,380
zato moramo storiti veliko mehurčki.

752
00:44:26,380 --> 00:44:30,190
Toda koliko korakov je, da bo trajalo v najslabšem primeru? >> [Študent] N kvadrat.

753
00:44:30,190 --> 00:44:32,550
To je n kvadrat, ker če mislite o tem,

754
00:44:32,550 --> 00:44:36,410
Če je seznam povsem nazaj - 8 je tukaj, 1 je tukaj -

755
00:44:36,410 --> 00:44:40,530
kot stvar začne mehurček, številka 8 se bo premaknil v to smer, na ta način,

756
00:44:40,530 --> 00:44:44,540
Na ta način, na ta način, ampak, če je številka 7 v najslabšem primeru?

757
00:44:44,540 --> 00:44:47,720
Tukaj je še vedno tam. Zato moramo to storiti znova in znova.

758
00:44:47,720 --> 00:44:53,190
In to je, če dobimo n korakih, potem n - 1 korakih, potem n - 2 korakih.

759
00:44:53,190 --> 00:44:55,960
In če se sprejme mojo besedo za to - da če jo pomnožimo nekako ven,

760
00:44:55,960 --> 00:45:00,110
to je približno n kvadrat na koncu še z nekaterimi drugimi pogoji, ki jih bomo samo za zdaj ne upoštevajo -

761
00:45:00,110 --> 00:45:06,890
nato pa v najslabšem primeru vrste mehurčkov n kvadrat, gor ali dol.

762
00:45:06,890 --> 00:45:09,490
Kaj pa najboljšem primeru z neke mehurček?

763
00:45:09,490 --> 00:45:13,050
Kaj je najboljši scenarij? Vse številke so že razporejene.

764
00:45:13,050 --> 00:45:15,920
In kaj je metodični sem, trik sem uporabil,

765
00:45:15,920 --> 00:45:20,110
zavedati, da sem storil nobenega dela in zato prenehati zgodaj?

766
00:45:20,110 --> 00:45:23,590
[Študent] Check it enkrat. Poglej >> enkrat. Ampak, kaj sem počel na poti?

767
00:45:23,590 --> 00:45:26,130
Bil sem sledenja, koliko zamenjav sem naredila.

768
00:45:26,130 --> 00:45:30,650
In spoznal sem, če sem ne štejemo nobenih zamenjav na prstih, potem pa sem naredil brez dela.

769
00:45:30,650 --> 00:45:34,300
Jaz zagotovo ne bi poskusil narediti nobenega dela spet, tako da sem lahko samo ustaviti.

770
00:45:34,300 --> 00:45:37,830
>> Torej v najboljšem primeru neke mehurčke, ko je seznam že urejen,

771
00:45:37,830 --> 00:45:41,530
kaj bi rekli oznako omega je najboljši primer teče čas?

772
00:45:41,530 --> 00:45:48,040
To je samo n. Moramo narediti nekaj dela, vendar smo le morali narediti v vrednosti 1 sprehod z dela.

773
00:45:48,040 --> 00:45:50,490
In tudi tu se bom, da zapustimo to del prazno.

774
00:45:50,490 --> 00:45:52,430
In zdaj izbor sort.

775
00:45:52,430 --> 00:45:56,010
Izbor vrste me je skubljenje najmanjšo osebo znova in znova.

776
00:45:56,010 --> 00:45:58,380
In kaj smo rekli teče čas je bil to?

777
00:45:58,380 --> 00:46:00,590
To je n kvadrat v najslabšem primeru.

778
00:46:00,590 --> 00:46:05,220
In na žalost, v najboljšem primeru se je tudi n kvadrat

779
00:46:05,220 --> 00:46:08,840
ker nimam neke vrste vsevednega Ob vsem svetu;

780
00:46:08,840 --> 00:46:13,140
Vem samo na popolno ponovitev, da sem res našel najmanjšo osebo.

781
00:46:13,140 --> 00:46:15,860
Torej, izbira neke vrste zanič v tem smislu,

782
00:46:15,860 --> 00:46:17,920
ampak glavo je, da je nekako intuitivno.

783
00:46:17,920 --> 00:46:21,470
To je zelo enostavno za kodiranje gor, ker vse, kar morate storiti, je napisati nekaj ugnezdena za zank,

784
00:46:21,470 --> 00:46:24,620
Značilno je, da gre skozi iščejo najmanjšega elementa

785
00:46:24,620 --> 00:46:27,840
in potem postavlja najmanjši element, kamor spada na koncu seznama.

786
00:46:27,840 --> 00:46:29,900
Torej tudi tukaj se bo kompromis.

787
00:46:29,900 --> 00:46:34,440
Čas, ki je potreben, da misliš, da se dejansko razvijajo in kaj je s pisanjem kode

788
00:46:34,440 --> 00:46:39,460
lahko zelo dobro vzame več časa, če želite boljše in hitrejše delovanje algoritma.

789
00:46:39,460 --> 00:46:41,780
>> Ampak, če ste res tako kot nekaj kode za hitro in umazano

790
00:46:41,780 --> 00:46:45,000
in kar nekako prevzeti neumna možno predstavo si lahko zamislite,

791
00:46:45,000 --> 00:46:47,580
ki bi lahko peljal nekaj minut kodo, vendar z velikih zbirk podatkov

792
00:46:47,580 --> 00:46:49,580
vaš algoritem lahko traja ure teči.

793
00:46:49,580 --> 00:46:51,690
In bi tudi jaz v šoli včasih te kompromise.

794
00:46:51,690 --> 00:46:55,660
To bi bilo 03:00, sem poskušal analizirati nekaj zelo velik nabor podatkov

795
00:46:55,660 --> 00:46:59,650
nanašajo na varnostne raziskave sem delal in je bil preživijo 5 minut

796
00:46:59,650 --> 00:47:03,210
poteg svoj program za analizo podatkov in zaspi

797
00:47:03,210 --> 00:47:08,420
ali preživijo 8 ur, da bi jo ravno prav, tako da deluje takoj in ne zaspi.

798
00:47:08,420 --> 00:47:10,530
In tako je tudi bilo nekako zavestne odločitve.

799
00:47:10,530 --> 00:47:12,740
Manj razvojni čas, več spanja.

800
00:47:12,740 --> 00:47:14,780
Če pogledam nazaj, se verjetno ne bi smela spodbujati, da

801
00:47:14,780 --> 00:47:19,120
ko je cilj tukaj je za višjo raven kakovosti kodeksa,

802
00:47:19,120 --> 00:47:21,280
ampak da tudi v realnem svetu je zelo razumen kompromis.

803
00:47:21,280 --> 00:47:25,130
Manj časa, manj zmogljivost ali obratno.

804
00:47:25,130 --> 00:47:28,110
Torej, tukaj smo končno dobili priložnost za pogovor o theta.

805
00:47:28,110 --> 00:47:32,830
Theta zapis je nekaj, računalniški znanstveniki lahko prinese v pogovoru

806
00:47:32,830 --> 00:47:36,160
ko veliki O in omega zgodi, da bo enako.

807
00:47:36,160 --> 00:47:40,160
Pravite, theta, da bo res poslali sporočilo, da je to nekako tesno povezani.

808
00:47:40,160 --> 00:47:43,340
Ne glede na to, ali je scenarij, dobro ali slabo, je to n kvadrat.

809
00:47:43,340 --> 00:47:46,510
Torej, to preprosto ni pomembno v teh zgodbah tukaj.

810
00:47:46,510 --> 00:47:48,560
Vstavitev vrsta je zadnja nas je zanimalo,

811
00:47:48,560 --> 00:47:50,830
kjer sem bil samo vstavljanje v vse na pravem mestu.

812
00:47:50,830 --> 00:47:54,930
V najboljšem primeru, kakšen je bil teče čas vstavitve vrste, kot smo ga videli tukaj?

813
00:47:54,930 --> 00:47:57,250
[Študent] najboljšem primeru? >> Najboljšem primeru.

814
00:47:57,250 --> 00:48:00,100
>> To je zato, ker n v najboljšem primeru vsak urejen,

815
00:48:00,100 --> 00:48:02,580
in Sammy in nihče drug Res je, da se premaknete na vse.

816
00:48:02,580 --> 00:48:04,610
Bili so že na svojem pravem mestu.

817
00:48:04,610 --> 00:48:08,570
Tako nekako vključitev v najboljšem primeru je v tem primeru n.

818
00:48:08,570 --> 00:48:12,770
Toda v najslabšem primeru pa nekako n kvadrat. Zakaj?

819
00:48:12,770 --> 00:48:16,230
Če moj seznam ljudi, je v obratnem vrstnem redu,

820
00:48:16,230 --> 00:48:21,260
Najprej sem začela s številko 8, ki sem ga vstavite ali jo v pravilnem položaju, kar je tukaj.

821
00:48:21,260 --> 00:48:25,270
Nekako sem prehod na strani. Ti fantje so nesortirani, on ali ona je urejeno.

822
00:48:25,270 --> 00:48:28,970
Ampak zdaj sem se zgodi, da ugotovite, kdo potem? >> [Študent] 7.

823
00:48:28,970 --> 00:48:31,250
7 v najslabšem primeru, ker je to v obratnem vrstnem redu.

824
00:48:31,250 --> 00:48:34,920
>> Torej, tukaj je 7. Kje 7 pripada? Zagotovo je za mano.

825
00:48:34,920 --> 00:48:39,460
Ampak zdaj 7 dejansko pripada ne takoj za mano, ampak za številko 8,

826
00:48:39,460 --> 00:48:41,880
tako da sem moral reči: "Oprosti, številka 8, lahko prosim premaknite na ta način

827
00:48:41,880 --> 00:48:44,640
"Da bi naredili prostor za 7?" Zdaj sem srečati 6.

828
00:48:44,640 --> 00:48:48,530
"Oh, oprostite, številka 8 in številko 7, se lahko premaknete, da naredite prostor za 6?"

829
00:48:48,530 --> 00:48:52,360
Torej, z drugimi besedami, z neke vstavljanja, čeprav ne delam veliko gibanja,

830
00:48:52,360 --> 00:48:56,330
ljudi za menoj delaš veliko več dela in da ima nekoga stalo časa.

831
00:48:56,330 --> 00:48:58,000
To bo stalo računalnik časa.

832
00:48:58,000 --> 00:49:01,450
Torej, v primeru vrste vstavitve še vedno trpijo.

833
00:49:01,450 --> 00:49:06,260
Če začnete sešteva skupno število korakov, smo na koncu hitting grobo n kvadrat

834
00:49:06,260 --> 00:49:11,160
ker so ti ljudje morali narediti prostor za človeka, ki se vstavi nazaj v ta seznam.

835
00:49:11,160 --> 00:49:15,960
In tako se je v tem primeru theta je samo ne uporablja za posamezne zgodbe v roki.

836
00:49:15,960 --> 00:49:21,100
To je vse lepo in prav. Imamo teh 3 različne načine govorimo o času delovanja.

837
00:49:21,100 --> 00:49:26,370
Toda kaj to pravzaprav pomeni realno, če bi dejansko poskušali kodo gor algoritem?

838
00:49:26,370 --> 00:49:31,620
>> Naj predlagajo, da obstaja še boljši algoritem tam

839
00:49:31,620 --> 00:49:33,740
da sama nekaj kompromisov.

840
00:49:33,740 --> 00:49:36,890
Mi bomo imenovali z zlivanjem, in to je nekako to čarobno algoritma

841
00:49:36,890 --> 00:49:42,840
da tako deluje hitreje nekako, in to je tako preprosto, da izrazijo, vsaj v Psevdokoda.

842
00:49:42,840 --> 00:49:46,900
Izvajanje te vrste algoritmov za združevanje se bo, kot sledi.

843
00:49:46,900 --> 00:49:50,860
Ko ste glede n elementov - N, N številk ljudi, ne glede na - prva se je duševno zdravje ček.

844
00:49:50,860 --> 00:49:56,340
Če je n manj kot 2, združi nekako samo ustavi. Se vrne, če se tako izrazim.

845
00:49:56,340 --> 00:50:00,830
Zakaj bi se ustavil, če je n manj kot 2? >> [Neslišno študentski odziv]

846
00:50:00,830 --> 00:50:04,480
Prav. In spet, n ni število na seznamu, n je velikost seznama.

847
00:50:04,480 --> 00:50:07,660
Če je n manjši od 2, kar pomeni, da vaš seznam je bodisi 1,

848
00:50:07,660 --> 00:50:09,640
če ste seveda razporejene če je številka 1,

849
00:50:09,640 --> 00:50:11,710
ali 0, v tem primeru ni nič rešiti,

850
00:50:11,710 --> 00:50:13,570
zato moramo te vrste primerjavi z osnovnim.

851
00:50:13,570 --> 00:50:20,350
Če je seznam tako kratek, da obstaja samo nič storiti, dobesedno ne naredi ničesar. Vrni se.

852
00:50:20,350 --> 00:50:25,090
Sicer razvrstiti v levi polovici elementov, nato pa razvrstiti na desni polovici elementov,

853
00:50:25,090 --> 00:50:27,410
spojite 2 razvrščeni polovic.

854
00:50:27,410 --> 00:50:32,130
>> Ta vrsta izgleda kot majhen goljufija, s katerim vas prosim, kako razvrstiti elemente

855
00:50:32,130 --> 00:50:34,900
in ti si mi povedal, "Razvrščanje v levi polovici, razvrstiti na desni polovici."

856
00:50:34,900 --> 00:50:37,240
Jaz pa: "Vse je v redu. Kako razvrstiti levo polovico?"

857
00:50:37,240 --> 00:50:40,670
"Razvrščanje v levi polovici levi polovici, razvrstiti na desni polovici levi polovici, nato pa storil."

858
00:50:40,670 --> 00:50:44,060
Ti si nekako ciklično opredelitvi, kaj to pomeni za razvrščanje,

859
00:50:44,060 --> 00:50:46,790
vendar se izkaže, da je pravzaprav odlična v tej zadevi.

860
00:50:46,790 --> 00:50:50,230
To ni res, da ta začarani krog se nikoli ne konča

861
00:50:50,230 --> 00:50:52,550
ker ne konča, ko? >> [Študent] Ko dosežete 1 stvar.

862
00:50:52,550 --> 00:50:54,220
Ko pridete do 1 stvar.

863
00:50:54,220 --> 00:50:57,850
Torej, čeprav lahko začnete z 8 ljudi in rečem, "Razvrščanje levo polovico teh ljudi,

864
00:50:57,850 --> 00:51:00,480
Ti ljudje 4 ", potem rečem," Kako rešiti levo polovico? "

865
00:51:00,480 --> 00:51:03,450
"No, nekako od 2 ljudi tukaj." In potem si kot: "V redu, v redu."

866
00:51:03,450 --> 00:51:05,520
"Kako rešiti levo polovico teh ljudi?"

867
00:51:05,520 --> 00:51:09,040
"Samo to razvrstite 1 oseba tukaj." Kaj je sijajno odkritje zdaj?

868
00:51:09,040 --> 00:51:13,050
Moram razvrstiti 1 osebo. Končano. Nimam nobene poklicne dejavnosti.

869
00:51:13,050 --> 00:51:16,580
Ampak zdaj moram rešiti to osebo, vendar pa si samska oseba, nič.

870
00:51:16,580 --> 00:51:21,490
>> Torej magija očitno je v tem tretjem koraku: združiti razvrščeni polovic.

871
00:51:21,490 --> 00:51:25,770
Tako nekako združiti jemlje to briljantno vpogled, da če si zlomil velik problem navzdol

872
00:51:25,770 --> 00:51:28,650
2 v manjše, enako velike težave

873
00:51:28,650 --> 00:51:32,710
in potem samo neke vrste lepilo manjše rešitve skupaj na koncu,

874
00:51:32,710 --> 00:51:34,720
Predlagam, da lahko naredimo še veliko, veliko bolje [prisluškovanje zvok]

875
00:51:34,720 --> 00:51:38,050
kakor koli vrste ali vstavitve izbor vrste.

876
00:51:38,050 --> 00:51:40,690
Sem bila dejansko ne upošteva, da se za pol ure, ampak jaz res ne vem, kaj se dogaja

877
00:51:40,690 --> 00:51:45,040
zunaj danes. [Whirring zvok] [smeh]

878
00:51:45,040 --> 00:51:49,660
Da vidimo, če lahko to vidimo z majhno pomočjo našega prijatelja Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Obstajata 2 velik korak v procesu vrste spajanja.

880
00:51:52,810 --> 00:51:56,400
Prvič, ves čas po delih seznam skodelic na polovici

881
00:51:56,400 --> 00:51:59,610
dokler ne bomo imeli kup seznamov s samo 1 skodelico v njih.

882
00:51:59,610 --> 00:52:02,150
Ne skrbite, če seznam vsebuje liho število

883
00:52:02,150 --> 00:52:04,830
in ne moreš narediti popolnoma čisti rez med njimi.

884
00:52:04,830 --> 00:52:08,740
Samo samovoljno izbirati, katere seznam vključiti dodatno skodelico noter

885
00:52:08,740 --> 00:52:11,320
Torej, kaj je razdeljen teh seznamov.

886
00:52:12,420 --> 00:52:14,570
Zdaj imamo 2 seznamov.

887
00:52:18,930 --> 00:52:20,930
Zdaj imamo 4 seznamov.

888
00:52:25,730 --> 00:52:28,740
Zdaj imamo 8 sezname z eno skodelico na vsakega seznama.

889
00:52:28,740 --> 00:52:31,520
Tako da je za 1. koraku.

890
00:52:31,520 --> 00:52:37,280
Za korak 2 smo ponovno združitev para seznamov s pomočjo algoritma za spajanje smo se naučili prej.

891
00:52:37,280 --> 00:52:44,320
Združitev 108 in 15 končamo s seznama 15, 108.

892
00:52:45,240 --> 00:52:51,330
Združitev 50 in 4 končamo s 4, 50.

893
00:52:51,330 --> 00:52:56,950
Združitev 8 in 42 smo na koncu z 8, 42.

894
00:52:57,790 --> 00:53:04,360
In združuje 23 in 16 smo na koncu z 16, 23.

895
00:53:04,360 --> 00:53:08,030
Zdaj so vsi naši seznami velikosti 2.

896
00:53:08,030 --> 00:53:10,980
Obvestilo, da je razvrščena vsaka od 4 seznamov,

897
00:53:10,980 --> 00:53:14,230
tako da lahko začnemo združuje parov seznamov znova.

898
00:53:14,230 --> 00:53:22,150
Združitev 15 in 108 ter 4 in 50 smo najprej vzeti 4, nato 15,

899
00:53:22,150 --> 00:53:26,250
nato 50, nato 108.

900
00:53:26,250 --> 00:53:33,020
Združitev 8, 42 in 16, 23 moramo najprej sprejeti 8, nato 16,

901
00:53:33,020 --> 00:53:37,170
nato 23, nato 42.

902
00:53:37,170 --> 00:53:42,490
Torej, zdaj imamo samo 2 seznamov velikosti 4, so razvrščeni od katerih vsaka.

903
00:53:42,490 --> 00:53:45,940
Zdaj smo združiti teh 2 seznamov.

904
00:53:45,940 --> 00:53:54,230
Najprej vzamemo 4, nato pa vzamemo 8, nato pa vzamemo 15

905
00:53:54,230 --> 00:54:05,280
in 16 ter 23 in 42 ter 50 in 108.

906
00:54:05,280 --> 00:54:09,020
In končamo. Zdaj imamo urejen seznam.

907
00:54:09,020 --> 00:54:13,740
>> Rob je nekako izkoristiti nekaj, kar še nismo opravili.

908
00:54:13,740 --> 00:54:16,540
Predlagano je bilo, ampak mi dejansko ni naredil.

909
00:54:16,540 --> 00:54:19,230
On je bil početje nekaj fizično z bonboni, da predlaga

910
00:54:19,230 --> 00:54:23,680
je bil porabi nekaj sredstev poleg časa. >> [Študent] vesolje. >> To je bil prostor.

911
00:54:23,680 --> 00:54:27,360
Dejstvo, da je imel tovrstne bi na ravni mizi, kjer je imel prostor tukaj

912
00:54:27,360 --> 00:54:31,960
in prostor tukaj je dejansko kar pomeni, da je z uporabo dvakrat toliko prostora

913
00:54:31,960 --> 00:54:36,390
kot kateri koli od naših algoritmov doslej - vstavljanje sortiranje, bubble sort, ali izbira sort -

914
00:54:36,390 --> 00:54:40,780
vendar je bil to vplivno dodaten prostor na vrsto premakniti stvari naprej in nazaj

915
00:54:40,780 --> 00:54:42,600
pri čemer pa stvari v red.

916
00:54:42,600 --> 00:54:47,540
In čeprav se zdi, kot da imamo na seznamu razvrščene, da so se počutili, kot da se je nekaj časa.

917
00:54:47,540 --> 00:54:51,060
V resnici je šlo Rob je bil ravno ta algoritem.

918
00:54:51,060 --> 00:54:56,780
Sprva je problem velikosti n, ga razdelimo na levi polovici in desni pol.

919
00:54:56,780 --> 00:54:59,380
To je, ko se je preselil v skodelice. Potem je ponovil ta proces.

920
00:54:59,380 --> 00:55:03,390
On je razdeljena na 4 2 2 sklopov sem in tja.

921
00:55:03,390 --> 00:55:08,520
Potem je ponovil ta proces in razdeljen v 2 sklopa 2 1 za vsako od teh različnih lončkov.

922
00:55:08,520 --> 00:55:11,000
In to je, če briljantno pojavi priložnost.

923
00:55:11,000 --> 00:55:15,840
Na tej točki v zgodbo, Rob je 8 seznamov velikosti 1,

924
00:55:15,840 --> 00:55:18,860
vsi, ki so že bili razvrščeni.

925
00:55:18,860 --> 00:55:20,630
>> Torej, kaj ti je nadaljevati narediti?

926
00:55:20,630 --> 00:55:25,260
Pairwise vzel ta urejen seznam in to urejen seznam in jih združiti.

927
00:55:25,260 --> 00:55:28,200
Nato je vzel tole in jih združiti, potem je to eno in jih združila,

928
00:55:28,200 --> 00:55:30,670
potem je to ena in jih združiti.

929
00:55:30,670 --> 00:55:32,390
In potem, kaj je naredil potem?

930
00:55:32,390 --> 00:55:36,580
Nato je ponovno združil večje liste in nato ponovno združila večje liste.

931
00:55:36,580 --> 00:55:41,170
In če misliš o tem samo intuitivno, za zdaj, kaj je res počne?

932
00:55:41,170 --> 00:55:45,450
Bil je tako, da se težave na pol na pol, na pol, na pol

933
00:55:45,450 --> 00:55:47,600
, da bi dobili te super majhne seznamov.

934
00:55:47,600 --> 00:55:51,290
Potem je bil nekako združuje dvojno, dvo-, dvo-, dvojno.

935
00:55:51,290 --> 00:55:54,120
Tako je bil dvakrat delal toliko dela, kot smo videli doslej

936
00:55:54,120 --> 00:55:56,930
z vsem, kar vključuje deli in vladaj, vendar nič posebnega.

937
00:55:56,930 --> 00:55:59,630
Dvakrat toliko, da delo ni nič takega. To je samo stalno prisotna.

938
00:55:59,630 --> 00:56:03,920
In podobno kot naš aritmetični izraz prej, bom samo za prehod iz stalne dejavnike

939
00:56:03,920 --> 00:56:10,170
kot vedno 2. Koga briga? Če je 2-krat v milijardah 2, ki je še vedno veliko korakov.

940
00:56:10,170 --> 00:56:13,160
Torej ta korak združitev zdi, da je ključni vpogled.

941
00:56:13,160 --> 00:56:17,000
Sprehodimo se skozi to samo številčno prej - Oh, to je, da se ne še nadaljevala.

942
00:56:17,000 --> 00:56:22,890
Sprehodimo se skozi to samo številčno da bi dejansko videli, kako ta igra ven.

943
00:56:22,890 --> 00:56:25,940
To je večinoma le malo ubogega človeka animacije.

944
00:56:25,940 --> 00:56:27,750
Naj bo predlagala to.

945
00:56:27,750 --> 00:56:31,480
Čas teče vrsta spajanje - moramo samo način govori o tem.

946
00:56:31,480 --> 00:56:34,380
To ni matematika, to je le neke vrste kratkega način izražanja sebe.

947
00:56:34,380 --> 00:56:39,080
Torej T predstavlja čas in n predstavlja kaj? >> [Študent] Velikost od -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] Obseg tega problema se je število ljudi.

949
00:56:41,400 --> 00:56:45,470
Torej sem trdil, da teče čas, da uredite n ljudi se bo 0 količina časa

950
00:56:45,470 --> 00:56:50,290
če je n manj kot 2, ker če imate 1 skodelico ali brez skodelice, nimaš nič za razvrščanje.

951
00:56:50,290 --> 00:56:55,160
Ampak na splošno, bom predlagal, da teče čas, da uredite n elementov

952
00:56:55,160 --> 00:56:59,350
se bo čas, potreben za razvrščanje v levi polovici plus desno polovico

953
00:56:59,350 --> 00:57:03,110
plus - kaj je to dodaten + n? >> [Študent] zlivanjem.

954
00:57:03,110 --> 00:57:07,260
[Malan] To je pravzaprav združitev, ker če imate n / 2 elementi tukaj

955
00:57:07,260 --> 00:57:11,500
in imate N / 2 elemente tukaj, koliko časa traja, da se ju združi?

956
00:57:11,500 --> 00:57:15,050
Tako kot Rob, morate oskubil tole tukaj, morda drobovja tukaj,

957
00:57:15,050 --> 00:57:17,120
Prebirati sem, drobovja sem, drobovja tukaj.

958
00:57:17,120 --> 00:57:19,400
Moraš se dotakniti vsakega od skodelic enkrat.

959
00:57:19,400 --> 00:57:22,030
In če obstaja 4 skodelice plus 4 skodelice, to je 8 skodelice

960
00:57:22,030 --> 00:57:25,200
ali, bolj splošno, 8 n skodelice.

961
00:57:25,200 --> 00:57:28,470
Tako lahko združujejo korak, ki ga predstavljajo kot n,

962
00:57:28,470 --> 00:57:31,330
in ki dobesedno pomeni, kolikokrat Rob fizično dotaknil

963
00:57:31,330 --> 00:57:33,410
ena od teh skodelic stiropora.

964
00:57:33,410 --> 00:57:35,850
Torej, kaj je zdaj to samovoljno primer.

965
00:57:35,850 --> 00:57:41,850
Če je 16 skodelic, kaj je čas delovanja razvrščanja, uporabljajo algoritem Rob je, 16 skodelic?

966
00:57:41,850 --> 00:57:44,710
To je 2-krat koliko časa traja, da razvrstite 8 skodelic

967
00:57:44,710 --> 00:57:46,920
saj imamo 8 skodelic tukaj, 8 skodelice tukaj.

968
00:57:46,920 --> 00:57:51,520
Ne vem, kako dolgo traja, da, tako da smo ga posploševati kot T za trenutek.

969
00:57:51,520 --> 00:57:53,320
Kdo ve, kaj je to?

970
00:57:53,320 --> 00:57:58,990
Ampak zdaj sem lahko nekako rekurzivno ali večkrat vprašati isto vprašanje.

971
00:57:58,990 --> 00:58:01,920
Koliko časa traja, da se razvrstite 8 skodelice?

972
00:58:01,920 --> 00:58:07,030
8 skodelic sem hotel reči, meni časa, ki je potreben, da razvrstite 4 skodelice plus 4 skodelice,

973
00:58:07,030 --> 00:58:08,880
Nato jih združiti skupaj.

974
00:58:08,880 --> 00:58:13,080
Prav. Gremo v krogu že. Kako dolgo traja, da razvrstite 4 skodelice?

975
00:58:13,080 --> 00:58:19,150
Čas, ki je potreben, da razvrstite 4 skodelice je 2 skodelice plus 2 skodelice sortiranje plus združitve procesa.

976
00:58:19,150 --> 00:58:21,440
Prav. Kako dolgo traja, da razvrstite 2 skodelice?

977
00:58:21,440 --> 00:58:26,290
2 skodelici je količina časa, ki je potreben, da razvrstite 1 skodelico plus čas, ki je potreben, da razvrstite eno skodelico

978
00:58:26,290 --> 00:58:29,040
plus količina časa, ki je potreben, da se združijo, ki je le 2.

979
00:58:29,040 --> 00:58:33,340
>> Prav. Zadnje vprašanje. Kako dolgo traja, da razvrstite 1 skodelico?

980
00:58:33,340 --> 00:58:37,260
Tu je osnova drži, da smo napovedali, da bomo zadeli prej.

981
00:58:37,260 --> 00:58:42,250
Dejstvo, da se ne dela nikakor rešiti najmanjših težav

982
00:58:42,250 --> 00:58:44,120
pomeni, da je zdaj nekako razred slogu šole,

983
00:58:44,120 --> 00:58:46,460
moremo iti začeti priklopom te številke nazaj noter

984
00:58:46,460 --> 00:58:50,630
Zdaj vemo, kaj T 1 je, da bom lahko priključite 0 za t 1.

985
00:58:50,630 --> 00:58:54,420
To mi bo dal odgovor na T 2, ki lahko nato priključite v višje.

986
00:58:54,420 --> 00:58:56,930
To mi bo dal T 4, kar sem lahko priključite na višje.

987
00:58:56,930 --> 00:58:58,920
To mi bo dal t 8, kar sem lahko priključite na višje.

988
00:58:58,920 --> 00:59:04,330
In če sem dejansko naredil, da izračunate s priklopom na teh odgovorov,

989
00:59:04,330 --> 00:59:08,590
Nato sem dobil T od 16 je 64 let.

990
00:59:08,590 --> 00:59:12,090
In kaj pomeni 64?

991
00:59:12,090 --> 00:59:15,700
Če je T 16, ja, to je 16-krat 4.

992
00:59:15,700 --> 00:59:20,120
Zato trdim, da je sedaj čas delovanja to stvar imenovano zlivanjem -

993
00:59:20,120 --> 00:59:22,590
in to se dogaja, da je fanciest od tistih, ki smo jih videli doslej -

994
00:59:22,590 --> 00:59:26,160
se dogaja, da se imenuje n log n

995
00:59:26,160 --> 00:59:31,140
ker lahko, kolikokrat Rob deljiva cel kup skodelic na pol? Prijavite n.

996
00:59:31,140 --> 00:59:34,370
To je isto, kot na primer imenika, je to isto, kot samo štetje npr.

997
00:59:34,370 --> 00:59:36,380
>> Kolikokrat lahko razdeli nekaj na pol?

998
00:59:36,380 --> 00:59:38,410
Vendar pa je ta združitev korak.

999
00:59:38,410 --> 00:59:42,920
Morda boste morali razdeliti na pol skodelice znova in znova in znova,

1000
00:59:42,920 --> 00:59:45,640
ampak vsakič, ko boste morali združiti.

1001
00:59:45,640 --> 00:59:48,270
In smo že povedali, da je združitev n skodelice meni n ukrepe

1002
00:59:48,270 --> 00:59:52,060
ker moraš Istrgnuti skodelico, Istrgnuti skodelico in imate na dotik vsako skodelico enkrat,

1003
00:59:52,060 --> 00:59:53,510
tako kot Rob storil.

1004
00:59:53,510 --> 00:59:59,430
Torej, če delamo nekaj Dnevnik n-krat in delamo n stvari na vsakem od teh iteracij,

1005
00:59:59,430 --> 01:00:03,090
vsako od teh halvings, imamo n-krat log n.

1006
01:00:03,090 --> 01:00:07,220
Torej, če priključite 16 V tem primeru je 16-krat prijavite od 16 -

1007
01:00:07,220 --> 01:00:10,600
Ne skrbite o tem, zakaj je temu tako, ker za zdaj še nisem pripraviti podlago -

1008
01:00:10,600 --> 01:00:16,100
ampak dnevnik osnove 2, 16 je 4, 16 krat 4 je 64 let.

1009
01:00:16,100 --> 01:00:22,350
Ampak po drugi strani, če bi smo mehurček vrste ali izbiro sort uredi ali vstavljanjem s 16 številkami,

1010
01:00:22,350 --> 01:00:26,420
kaj bi bilo, če teče čas n 16?

1011
01:00:26,420 --> 01:00:33,310
To bi bilo 16 kvadratov, kar je 256, ki tudi če ni povsem sledil vse matematike,

1012
01:00:33,310 --> 01:00:38,390
256 je večji od 64 let. To je res čarobna hrana za s seboj tukaj.

1013
01:00:38,390 --> 01:00:41,990
In zavedati, da delajo preko tega v manjših primerov, ko se bo na pset

1014
01:00:41,990 --> 01:00:44,260
Zato je toliko bolj intuitivno.

1015
01:00:44,260 --> 01:00:49,070
Toda kaj to v resnici pomeni v smislu občutek tega algoritma je:

1016
01:00:49,070 --> 01:00:54,520
Če smo dejansko pogledamo vrste spajanja - Naj ga povlecite v to okno tukaj -

1017
01:00:54,520 --> 01:00:58,560
To je nekoliko drugačen primer, s katerim smo vsi 3 teh algoritmov -

1018
01:00:58,560 --> 01:01:01,440
mehurček, izbire in združitev - le drug ob drugem.

1019
01:01:01,440 --> 01:01:03,740
>> Vsi so začeli z naključnimi palice, in to je dobro.

1020
01:01:03,740 --> 01:01:06,240
Nihče ni bistveno prednost pred drugimi.

1021
01:01:06,240 --> 01:01:09,500
Grem v trenutku, kliknite vsako od teh animacij - Start Start, Start -

1022
01:01:09,500 --> 01:01:13,270
kakor hitro sem lahko, tako da, v grobem, da vse skupaj začelo ob istem času,

1023
01:01:13,270 --> 01:01:17,450
in kaj menijo, da je mehurček razvrstite v primeru hujše časa vožnje je kaj? >> [Študent] N kvadrat.

1024
01:01:17,450 --> 01:01:21,560
N kvadrat. Izbirne razvrstite v najslabšem primeru teče čas je? N kvadrat.

1025
01:01:21,560 --> 01:01:25,150
In zlivanjem je očitno - tudi če ni povsem upoštevati vse math zdaj,

1026
01:01:25,150 --> 01:01:30,610
da bomo postali veliko bolj intuitivno skozi čas - je trdimo, n log n-krat.

1027
01:01:30,610 --> 01:01:35,210
In ker log n je strogo manjši od n, ko imamo velike številke,

1028
01:01:35,210 --> 01:01:40,230
n log n-krat manjša od časov N ali n kvadrat.

1029
01:01:40,230 --> 01:01:44,410
Torej, kaj je občutek, da pravzaprav bolje algoritem glede časa vožnje,

1030
01:01:44,410 --> 01:01:50,380
n log n-krat v primerjavi z n kvadrat? Pa gremo. Kliknite, kliknite, kliknite.

1031
01:01:55,690 --> 01:01:58,650
>> To pomeni, da uporabite nekaj podobnega vrste spajanja.

1032
01:01:58,650 --> 01:02:01,680
Imamo trenutek. Pa poglejmo, kaj se dogaja tukaj.

1033
01:02:09,440 --> 01:02:12,440
[Smeh] Čigav je denar od vrste mehurček?

1034
01:02:14,960 --> 01:02:16,730
Prej je odvisno od vhoda včasih.

1035
01:02:16,730 --> 01:02:18,120
Pa poglejmo.

1036
01:02:18,120 --> 01:02:23,320
Daj no. Zdi se, kot da se dohiteva. >> [Študent] Pojdi, mehurček vrste!

1037
01:02:23,320 --> 01:02:27,370
[Učenci godrnjajo]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Ja, ja.

1039
01:02:29,120 --> 01:02:34,520
[Učenci godrnjajo] Gremo, gremo, gremo!

1040
01:02:37,210 --> 01:02:40,450
[Vsi navijajo] [aplavz]

1041
01:02:40,450 --> 01:02:46,240
Torej, zdaj z 1 zadnji, končni demo, če je to precej zapleteno zaviti vaš um okoli matematiki

1042
01:02:46,240 --> 01:02:49,280
ali vrsta vizualizacije tam, lahko dejansko slišati hitrosti

1043
01:02:49,280 --> 01:02:51,000
različnih algoritmov drugače.

1044
01:02:51,000 --> 01:02:53,900
To je animacija nekdo, ki dejansko zveni sodelavci

1045
01:02:53,900 --> 01:02:56,980
s procesom zamenjavam in višine palic.

1046
01:02:56,980 --> 01:03:00,440
Kot bomo videli tu, tam je še nekaj algoritmov tam, da so ljudje mislil.

1047
01:03:00,440 --> 01:03:03,660
Ta prva se bo vstavljanje sortiranje in to bo letel skozi

1048
01:03:03,660 --> 01:03:07,090
in vam zvočni občutek, kako te različne delo algoritmov.

1049
01:03:07,090 --> 01:03:09,080
Tukaj je vstavljanje vrste.

1050
01:03:09,080 --> 01:03:18,410
[Elektronske piskanje]

1051
01:03:18,410 --> 01:03:20,730
[Malan] bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Hitrejši elektronsko piskanje]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Izbira vrste.

1054
01:03:48,950 --> 01:04:03,580
[Hitrejši elektronsko piskanje]

1055
01:04:03,580 --> 01:04:05,770
[Malan] zlivanjem.

1056
01:04:05,770 --> 01:04:17,270
[Elektronske piskanje]

1057
01:04:17,270 --> 01:04:20,180
[Piskanje upočasni] [smeh]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome sort.

1059
01:04:22,590 --> 01:04:38,580
[Elektronske piskanje]

1060
01:04:39,740 --> 01:04:46,150
>> To je CS50. Vidimo se naslednji teden. [Ploskanje in navijanje]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]