1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Olet varmaan kuullut puhuttavan nopea tai tehokas algoritmi

2
00:00:10,950 --> 00:00:13,090
toteuttamisesta oman tietyn tehtävän,

3
00:00:13,090 --> 00:00:16,110
mutta mitä se tarkoittaa algoritmin olla nopea tai tehokas?

4
00:00:16,110 --> 00:00:18,580
No, se ei puhu mittauksen reaaliajassa,

5
00:00:18,580 --> 00:00:20,500
kuten sekuntia tai minuuttia.

6
00:00:20,500 --> 00:00:22,220
Tämä johtuu siitä, tietokonelaitteiston

7
00:00:22,220 --> 00:00:24,260
ja ohjelmiston vaihdella suuresti.

8
00:00:24,260 --> 00:00:26,020
Oma ohjelma voisi ajaa hitaammin kuin sinun,

9
00:00:26,020 --> 00:00:28,000
koska olen käynnissä sitä vanhempi tietokone,

10
00:00:28,000 --> 00:00:30,110
tai koska satun pelata online-videopeli

11
00:00:30,110 --> 00:00:32,670
samaan aikaan, joka on kahmimalla kaikki minun muistiin,

12
00:00:32,670 --> 00:00:35,400
tai voisin olla käynnissä oman ohjelman kautta eri ohjelmistojen

13
00:00:35,400 --> 00:00:37,550
joka on yhteydessä koneen eri alhaisella tasolla.

14
00:00:37,550 --> 00:00:39,650
Se on kuin vertaisi omenoita ja appelsiineja.

15
00:00:39,650 --> 00:00:41,940
Vain koska minun hitaampi tietokone kestää

16
00:00:41,940 --> 00:00:43,410
kuin sinun antaa takaisin vastausta

17
00:00:43,410 --> 00:00:45,510
ei tarkoita sinulla on tehokkaampi algoritmi.

18
00:00:45,510 --> 00:00:48,830
>> Joten, koska emme voi suoraan verrata runtimes ohjelmien

19
00:00:48,830 --> 00:00:50,140
sekunnin tai minuutin,

20
00:00:50,140 --> 00:00:52,310
Miten voimme vertailla 2 eri algoritmeja

21
00:00:52,310 --> 00:00:55,030
riippumatta niiden laitteita tai ohjelmistoja ympäristölle?

22
00:00:55,030 --> 00:00:58,000
Voit luoda tasaisemman tapa mitata algoritmisen tehokkuutta,

23
00:00:58,000 --> 00:01:00,360
tietotekniikan tutkijoita ja matemaatikot ovat kehittäneet

24
00:01:00,360 --> 00:01:03,830
käsitteet mittaamiseksi asymptoottinen monimutkaisuus ohjelman

25
00:01:03,830 --> 00:01:06,110
ja merkintä nimeltään "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
kuvaamiseen tässä.

27
00:01:08,320 --> 00:01:10,820
Muodollinen määritelmä on, että funktio f (x)

28
00:01:10,820 --> 00:01:13,390
toimii suuruusluokkaa g (x)

29
00:01:13,390 --> 00:01:15,140
jos on olemassa joitakin (x) arvo, x ₀ ja

30
00:01:15,140 --> 00:01:17,630
Joissakin vakio, C, jonka

31
00:01:17,630 --> 00:01:19,340
f (x) on pienempi tai yhtä suuri kuin

32
00:01:19,340 --> 00:01:21,230
että vakio kertaa g (x)

33
00:01:21,230 --> 00:01:23,190
kaikilla x on suurempi kuin x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Mutta älä pelkää pois virallisen määritelmän.

35
00:01:25,290 --> 00:01:28,020
Mitä tämä oikeastaan ​​tarkoittaa vähemmän teoreettisesti?

36
00:01:28,020 --> 00:01:30,580
No, se on pohjimmiltaan tapa analysoida

37
00:01:30,580 --> 00:01:33,580
kuinka nopeasti ohjelman runtime kasvaa asymptoottisesti.

38
00:01:33,580 --> 00:01:37,170
Toisin sanoen, kuten kokoa panosten kasvaa kohti ääretöntä,

39
00:01:37,170 --> 00:01:41,390
sanoa, olet lajittelu joukko koko 1000 verrattuna joukko koko 10.

40
00:01:41,390 --> 00:01:44,950
Miten runtime oman ohjelman kasvaa?

41
00:01:44,950 --> 00:01:47,390
Oletetaan esimerkiksi, laskee merkkien määrä

42
00:01:47,390 --> 00:01:49,350
in string yksinkertaisin tapa

43
00:01:49,350 --> 00:01:51,620
 kävelemällä läpi koko merkkijono

44
00:01:51,620 --> 00:01:54,790
kirjain-by-kirjain ja lisäämällä 1 laskuri kunkin merkin.

45
00:01:55,700 --> 00:01:58,420
Tämä algoritmi on sanonut ajaa lineaarisessa ajassa

46
00:01:58,420 --> 00:02:00,460
suhteen merkkien määrä,

47
00:02:00,460 --> 00:02:02,670
'N' merkkijono.

48
00:02:02,670 --> 00:02:04,910
Lyhyesti sanottuna, se toimii O (n).

49
00:02:05,570 --> 00:02:07,290
Miksi on näin?

50
00:02:07,290 --> 00:02:09,539
No, käyttäen tätä lähestymistapaa, aika, joka tarvitaan

51
00:02:09,539 --> 00:02:11,300
kulkemaan koko merkkijono

52
00:02:11,300 --> 00:02:13,920
on verrannollinen merkkien määrä.

53
00:02:13,920 --> 00:02:16,480
Counting merkkien määrä 20-merkkijonon

54
00:02:16,480 --> 00:02:18,580
vie kaksi kertaa niin kauan kuin se kestää

55
00:02:18,580 --> 00:02:20,330
laskea merkkiä 10-merkkinen merkkijono,

56
00:02:20,330 --> 00:02:23,000
koska sinulla on katsoa kaikki merkit

57
00:02:23,000 --> 00:02:25,740
ja kukin merkki vie saman verran aikaa tarkastella.

58
00:02:25,740 --> 00:02:28,050
Kun lisäät merkkien määrä,

59
00:02:28,050 --> 00:02:30,950
runtime kasvaa lineaarisesti tulo pituus.

60
00:02:30,950 --> 00:02:33,500
>> Nyt, kuvittele jos päätät, että lineaarisen ajan,

61
00:02:33,500 --> 00:02:36,390
O (n), ei vain ollut tarpeeksi nopea sinulle?

62
00:02:36,390 --> 00:02:38,750
Ehkä olet tallentamiseen valtava jouset,

63
00:02:38,750 --> 00:02:40,450
ja sinulla ei ole varaa ylimääräistä aikaa kestäisi

64
00:02:40,450 --> 00:02:44,000
kulkemaan kaikkien niiden merkkien laskemisen yhden by-one.

65
00:02:44,000 --> 00:02:46,650
Joten, päätät kokeilla jotain erilaista.

66
00:02:46,650 --> 00:02:49,270
Mitä jos tapahtuisi jo tallentaa monta merkkiä

67
00:02:49,270 --> 00:02:52,690
in string, eli vuonna muuttuja nimeltä "len"

68
00:02:52,690 --> 00:02:54,210
varhaisessa vaiheessa ohjelmaan

69
00:02:54,210 --> 00:02:57,800
ennen kuin edes tallentaa aivan ensimmäinen merkki merkkijono?

70
00:02:57,800 --> 00:02:59,980
Sitten kaikki sinun täytyy tehdä nyt selvittää merkkijonon pituus,

71
00:02:59,980 --> 00:03:02,570
on tarkistaa, mitä muuttujan arvo on.

72
00:03:02,570 --> 00:03:05,530
Sinulla ei tarvitse katsoa merkkijonon itse ollenkaan,

73
00:03:05,530 --> 00:03:08,160
ja päästä arvo muuttujan kuten LEN pidetään

74
00:03:08,160 --> 00:03:11,100
asymptoottisesti vakio toiminnassa,

75
00:03:11,100 --> 00:03:13,070
tai O (1).

76
00:03:13,070 --> 00:03:17,110
Miksi on näin? No, muistaa, mitä asymptoottinen monimutkaisuus tarkoittaa.

77
00:03:17,110 --> 00:03:19,100
Miten runtime muutoksen koko

78
00:03:19,100 --> 00:03:21,400
teidän tulot kasvaa?

79
00:03:21,400 --> 00:03:24,630
>> Sano yritit saada merkkien määrä isompi merkkijono.

80
00:03:24,630 --> 00:03:26,960
No, se ei väliä kuinka suuri teet merkkijono,

81
00:03:26,960 --> 00:03:28,690
jopa miljoona merkkiä pitkä,

82
00:03:28,690 --> 00:03:31,150
kaikki sinun täytyy tehdä löytää merkkijonon pituus tätä lähestymistapaa,

83
00:03:31,150 --> 00:03:33,790
on lukea muuttujan arvo len-

84
00:03:33,790 --> 00:03:35,440
jotka olet jo tehnyt.

85
00:03:35,440 --> 00:03:38,200
Tulo pituus, joka on, että merkkijonon pituus yrität löytää,

86
00:03:38,200 --> 00:03:41,510
ei vaikuta lainkaan kuinka nopeasti ohjelma toimii.

87
00:03:41,510 --> 00:03:44,550
Tämä osa ohjelmaa kulkisi yhtä nopeaa yhden merkkijonon

88
00:03:44,550 --> 00:03:46,170
ja tuhannen merkkijonon,

89
00:03:46,170 --> 00:03:49,140
ja siksi tämä ohjelma kutsutaan käynnissä jatkuvasti ajan

90
00:03:49,140 --> 00:03:51,520
suhteessa sisääntulon koko.

91
00:03:51,520 --> 00:03:53,920
>> Tietenkin siellä haittana.

92
00:03:53,920 --> 00:03:55,710
Vietät lisää muistia tietokoneeseen

93
00:03:55,710 --> 00:03:57,380
tallennetaan muuttujan

94
00:03:57,380 --> 00:03:59,270
ja ylimääräistä aikaa se vie

95
00:03:59,270 --> 00:04:01,490
tehdä todellinen varastoinnin muuttujan

96
00:04:01,490 --> 00:04:03,390
mutta kohta on edelleen voimassa,

97
00:04:03,390 --> 00:04:05,060
selvittää kuinka kauan merkkijono oli

98
00:04:05,060 --> 00:04:07,600
ei riipu merkkijonon pituus lainkaan.

99
00:04:07,600 --> 00:04:10,720
Niin, se kulkee O (1) tai vakio ajan.

100
00:04:10,720 --> 00:04:13,070
Tämä ei tietenkään tarvitse tarkoittaa

101
00:04:13,070 --> 00:04:15,610
että koodi toimii 1 askeleen,

102
00:04:15,610 --> 00:04:17,470
mutta ei väliä kuinka monta askelta on,

103
00:04:17,470 --> 00:04:20,019
jos se ei muutu koko panosten

104
00:04:20,019 --> 00:04:23,420
se on silti asymptoottisesti vakio jota edustan O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kuten arvata saattaa,

106
00:04:25,120 --> 00:04:27,940
on olemassa monia erilaisia ​​Big O runtimes mitata algoritmit.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmit ovat asymptoottisesti hitaampia kuin O (n) algoritmeja.

108
00:04:32,980 --> 00:04:35,910
Toisin sanoen, kuten elementtien määrä (n) kasvaa,

109
00:04:35,910 --> 00:04:39,280
lopulta O (n) ² algoritmeja vie enemmän aikaa

110
00:04:39,280 --> 00:04:41,000
kuin O (n) algoritmit suorittaa.

111
00:04:41,000 --> 00:04:43,960
Tämä ei tarkoita O (n) algoritmit aina ajaa nopeammin

112
00:04:43,960 --> 00:04:46,410
kuin O (n) ² algoritmeja, jopa samassa ympäristössä,

113
00:04:46,410 --> 00:04:48,080
samalla laitteisto.

114
00:04:48,080 --> 00:04:50,180
Ehkä pieni panos koot,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmi saattaisi toimia nopeammin,

116
00:04:52,900 --> 00:04:55,450
mutta, lopulta, kun tulo koko kasvaa

117
00:04:55,450 --> 00:04:58,760
kohti ääretöntä, O (n) ² algoritmin runtime

118
00:04:58,760 --> 00:05:02,000
lopulta varjoonsa kulkuaikaerojen O (n)-algoritmia.

119
00:05:02,000 --> 00:05:04,230
Aivan kuten mikä tahansa asteen matemaattinen funktio

120
00:05:04,230 --> 00:05:06,510
 lopulta ohittaa minkä tahansa lineaarinen funktio,

121
00:05:06,510 --> 00:05:09,200
ei väliä kuinka paljon etumatkaa lineaarinen funktio alkaa pois.

122
00:05:10,010 --> 00:05:12,000
Jos olet työskennellyt suuria tietomääriä,

123
00:05:12,000 --> 00:05:15,510
algoritmeja, jotka toimivat O (n) ² aikaa voi todella päätyä hidastamatta ohjelmaa,

124
00:05:15,510 --> 00:05:17,770
mutta pienellä panoksella kokoja,

125
00:05:17,770 --> 00:05:19,420
luultavasti ei edes huomaa.

126
00:05:19,420 --> 00:05:21,280
>> Toinen asymptoottinen monimutkaisuus on,

127
00:05:21,280 --> 00:05:24,420
logaritminen aikaa, O (log n).

128
00:05:24,420 --> 00:05:26,340
Esimerkki algoritmi, joka suorittaa tämän nopeasti

129
00:05:26,340 --> 00:05:29,060
on klassinen binäärihakupuu algoritmi,

130
00:05:29,060 --> 00:05:31,850
löytää osa jo lajiteltu luettelo elementtejä.

131
00:05:31,850 --> 00:05:33,400
>> Jos et tiedä mitä binäärihakupuu tekee,

132
00:05:33,400 --> 00:05:35,170
Selitän sen teille todella nopeasti.

133
00:05:35,170 --> 00:05:37,020
Sanotaan etsit numero 3

134
00:05:37,020 --> 00:05:40,200
Tässä joukko kokonaislukuja.

135
00:05:40,200 --> 00:05:42,140
Siinä tarkastellaan keskellä alkiota

136
00:05:42,140 --> 00:05:46,830
ja kysyy, "Onko elementin haluan suurempi, yhtä suuri tai pienempi kuin tämä?"

137
00:05:46,830 --> 00:05:49,150
Jos se on sama, niin hyvä. Löysit elementti, ja olet valmis.

138
00:05:49,150 --> 00:05:51,300
Jos se on suurempi, niin tiedät elementti

139
00:05:51,300 --> 00:05:53,440
on oltava oikeassa reunassa array,

140
00:05:53,440 --> 00:05:55,200
ja voit vain katsoa, ​​että tulevaisuudessa,

141
00:05:55,200 --> 00:05:57,690
ja jos se on pienempi, niin tiedät sen on oltava vasemmalla puolella.

142
00:05:57,690 --> 00:06:00,980
Tämä prosessi toistetaan sitten kanssa pienemmän koon array

143
00:06:00,980 --> 00:06:02,870
kunnes oikea elementti on löytynyt.

144
00:06:08,080 --> 00:06:11,670
>> Tämä tehokas algoritmi leikkaa jonon pituus on puoli jokaisen operaation.

145
00:06:11,670 --> 00:06:14,080
Joten, löytää osa lajitellaan joukko koko 8,

146
00:06:14,080 --> 00:06:16,170
enintään (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
tai 3 näistä toimista,

148
00:06:18,450 --> 00:06:22,260
tarkkailun keskimmäinen elementti, sitten leikkaamalla array puoli tarvitaan,

149
00:06:22,260 --> 00:06:25,670
taas joukko koko 16 vie (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
tai 4 toimintaa.

151
00:06:27,480 --> 00:06:30,570
Se on vain 1 enemmän toiminnassa kaksinkertaistui-size array.

152
00:06:30,570 --> 00:06:32,220
Koko kaksinkertaistui array

153
00:06:32,220 --> 00:06:35,160
lisää runtime vain 1 kimpale tämän koodin.

154
00:06:35,160 --> 00:06:37,770
Jälleen tarkistaa keskimmäinen elementti luettelosta ja halkaisu.

155
00:06:37,770 --> 00:06:40,440
Niin, se sanoi toimimaan logaritminen aika,

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Mutta hetkinen, te sanotte,

158
00:06:44,270 --> 00:06:47,510
ei tämä riipu siitä, missä luettelossa elementti etsit on?

159
00:06:47,510 --> 00:06:50,090
Mitä jos ensimmäinen elementti sinä katsot sattuu olemaan oikea?

160
00:06:50,090 --> 00:06:52,040
Sitten se kestää vain 1 käytössä,

161
00:06:52,040 --> 00:06:54,310
ei väliä kuinka iso lista on.

162
00:06:54,310 --> 00:06:56,310
>> No, siksi tietojenkäsittelyasiantuntijat enemmän ehdot

163
00:06:56,310 --> 00:06:58,770
varten asymptoottinen monimutkaisuus jotka heijastavat parhaiten tapaus

164
00:06:58,770 --> 00:07:01,050
ja pahimman tapauksen suorituskyky algoritmin.

165
00:07:01,050 --> 00:07:03,320
Oikeammin, ylä-ja alarajojen

166
00:07:03,320 --> 00:07:05,090
on runtime.

167
00:07:05,090 --> 00:07:07,660
Parhaassa tapauksessa binäärihakupuu, meidän elementti on

168
00:07:07,660 --> 00:07:09,330
tuolla keskellä,

169
00:07:09,330 --> 00:07:11,770
ja saat sen jatkuvasti ajan

170
00:07:11,770 --> 00:07:14,240
siitä, kuinka iso loput joukko on.

171
00:07:15,360 --> 00:07:17,650
Symboli käyttää tähän on Ω.

172
00:07:17,650 --> 00:07:19,930
Joten, tämä algoritmi on mainittu toimimaan Ω (1).

173
00:07:19,930 --> 00:07:21,990
Parhaassa tapauksessa se löytää elementti nopeasti,

174
00:07:21,990 --> 00:07:24,200
ei väliä kuinka suuri joukko on,

175
00:07:24,200 --> 00:07:26,050
mutta pahimmassa tapauksessa,

176
00:07:26,050 --> 00:07:28,690
se on suorittaa (log n) kohdalta tarkastuksia

177
00:07:28,690 --> 00:07:31,030
on array löytää oikea elementti.

178
00:07:31,030 --> 00:07:34,270
Pahin ylärajat viitataan isolla "O", että tiedät jo.

179
00:07:34,270 --> 00:07:38,080
Niin, se on O (log n), mutta Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Lineaarista hakua, sitä vastoin,

181
00:07:40,680 --> 00:07:43,220
jossa kävelee jokaisen alkiota

182
00:07:43,220 --> 00:07:45,170
löytää haluamasi,

183
00:07:45,170 --> 00:07:47,420
on paras Ω (1).

184
00:07:47,420 --> 00:07:49,430
Jälleen ensimmäinen elementti haluat.

185
00:07:49,430 --> 00:07:51,930
Niin, se ei ole väliä kuinka suuri joukko on.

186
00:07:51,930 --> 00:07:54,840
Pahimmassa tapauksessa se viimeinen alkio.

187
00:07:54,840 --> 00:07:58,560
Joten, sinun täytyy käydä läpi kaikki n elementtejä array löytää se,

188
00:07:58,560 --> 00:08:02,170
kuten jos etsit 3.

189
00:08:04,320 --> 00:08:06,030
Niin, se kulkee O (n) aika

190
00:08:06,030 --> 00:08:09,330
koska se on verrannollinen elementtien lukumäärä jono.

191
00:08:10,800 --> 00:08:12,830
>> Yksi symboli on käytetty Θ.

192
00:08:12,830 --> 00:08:15,820
Tätä voidaan käyttää kuvaamaan algoritmeja, joissa paras ja pahimmassa tapauksessa

193
00:08:15,820 --> 00:08:17,440
ovat samat.

194
00:08:17,440 --> 00:08:20,390
Tämä tapaus on merkkijonon pituus algoritmit puhuimme aiemmin.

195
00:08:20,390 --> 00:08:22,780
Eli jos me säilytä se muuttuja ennen

196
00:08:22,780 --> 00:08:25,160
me tallentaa merkkijonon ja käyttää sitä myöhemmin jatkuvasti ajan.

197
00:08:25,160 --> 00:08:27,920
Ei ole väliä mitä numero

198
00:08:27,920 --> 00:08:30,130
olemme tallentaminen muuttujan, meidän täytyy katsoa sitä.

199
00:08:33,110 --> 00:08:35,110
Parhaassa tapauksessa on, katsomme sitä

200
00:08:35,110 --> 00:08:37,120
ja löytää langan pituutta.

201
00:08:37,120 --> 00:08:39,799
Joten Ω (1) tai parhaassa tapauksessa vakio ajan.

202
00:08:39,799 --> 00:08:41,059
Pahimmassa tapauksessa on,

203
00:08:41,059 --> 00:08:43,400
katsomme sitä ja löytää merkkijonon pituus.

204
00:08:43,400 --> 00:08:47,300
Niin, O (1) tai vakio aikaa pahimmassa tapauksessa.

205
00:08:47,300 --> 00:08:49,180
Joten, koska parhaassa tapauksessa ja pahimmassa tapauksessa ovat samat,

206
00:08:49,180 --> 00:08:52,520
Tämän voidaan sanoa ajaa Θ (1) aika.

207
00:08:54,550 --> 00:08:57,010
>> Yhteenvetona, meillä on hyviä tapoja syystä noin koodeja tehokkuutta

208
00:08:57,010 --> 00:09:00,110
tietämättä mitään reaalimaailman aikaa he ottavat juosta,

209
00:09:00,110 --> 00:09:02,270
johon vaikuttaa paljon ulkopuoliset tekijät,

210
00:09:02,270 --> 00:09:04,190
mukaan lukien erilaiset laitteet, ohjelmistot,

211
00:09:04,190 --> 00:09:06,040
tai yksityiskohtien koodisi.

212
00:09:06,040 --> 00:09:08,380
Lisäksi sen avulla voimme järkeillä hyvin siitä, mitä tapahtuu

213
00:09:08,380 --> 00:09:10,180
kun koko panosten kasvaessa.

214
00:09:10,180 --> 00:09:12,490
>> Jos käytät O (n) ² algoritmi,

215
00:09:12,490 --> 00:09:15,240
tai pahempaa, O (2 ⁿ) algoritmi,

216
00:09:15,240 --> 00:09:17,170
yksi nopeimmin kasvavista tyypit,

217
00:09:17,170 --> 00:09:19,140
sinun todella alkaa huomata hidastumiseen

218
00:09:19,140 --> 00:09:21,220
Kun aloitat työskentelyn suurempia tietomääriä.

219
00:09:21,220 --> 00:09:23,590
>> Se asymptoottinen monimutkaisuutta. Kiitos.