1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Sa oled ilmselt kuulnud inimesed räägivad kiiresti või tõhus algoritm

2
00:00:10,950 --> 00:00:13,090
teostamiseks oma konkreetne ülesanne,

3
00:00:13,090 --> 00:00:16,110
Aga mida täpselt tähendab see algoritm peab olema kiire või tõhus?

4
00:00:16,110 --> 00:00:18,580
Noh, see ei räägi mõõtmine reaalajas

5
00:00:18,580 --> 00:00:20,500
nagu sekundites või minutites.

6
00:00:20,500 --> 00:00:22,220
Seda seetõttu, et arvuti riistvara

7
00:00:22,220 --> 00:00:24,260
ja tarkvara väga oluliselt erineda.

8
00:00:24,260 --> 00:00:26,020
Minu programm võib käivitada aeglasem kui sinu oma,

9
00:00:26,020 --> 00:00:28,000
sest ma olen töötab see vanem arvuti,

10
00:00:28,000 --> 00:00:30,110
või sellepärast, et ma juhtumisi mängib online videomäng

11
00:00:30,110 --> 00:00:32,670
samal ajal, mis on hogging kõik mu mälu,

12
00:00:32,670 --> 00:00:35,400
või ma võib olla töötab minu programm läbi erinevate tarkvara

13
00:00:35,400 --> 00:00:37,550
mis suhtleb masin erinevalt madalal tasemel.

14
00:00:37,550 --> 00:00:39,650
See on nagu võrrelda õunu ja apelsine.

15
00:00:39,650 --> 00:00:41,940
Lihtsalt, sest minu aeglasem arvuti võtab kauem

16
00:00:41,940 --> 00:00:43,410
kui sinu oma tagasi anda vastus

17
00:00:43,410 --> 00:00:45,510
ei tähenda, teil on tõhusam algoritm.

18
00:00:45,510 --> 00:00:48,830
>> Niisiis, kuna me ei saa otseselt võrrelda runtimes programmide

19
00:00:48,830 --> 00:00:50,140
sekundites või minutites,

20
00:00:50,140 --> 00:00:52,310
Kuidas me võrrelda 2 erinevat algoritmid

21
00:00:52,310 --> 00:00:55,030
sõltumata nende riistvara või tarkvara keskkonnas?

22
00:00:55,030 --> 00:00:58,000
Et luua ühtne viis mõõta algoritmilise tõhususe,

23
00:00:58,000 --> 00:01:00,360
arvuti teadlased ja matemaatikud on välja töötatud

24
00:01:00,360 --> 00:01:03,830
mõisted mõõtmiseks asümptootilisest keerukus programmi

25
00:01:03,830 --> 00:01:06,110
ja märge "suure Ohnotation"

26
00:01:06,110 --> 00:01:08,320
kirjeldamiseks seda.

27
00:01:08,320 --> 00:01:10,820
Formaalne definitsioon on, et funktsioon f (x)

28
00:01:10,820 --> 00:01:13,390
töötab järjekorras g (x)

29
00:01:13,390 --> 00:01:15,140
kui on olemas mõned (x) väärtus, x ₀ ja

30
00:01:15,140 --> 00:01:17,630
mingite konstantide, c, mille

31
00:01:17,630 --> 00:01:19,340
f (x) on väiksem või võrdne

32
00:01:19,340 --> 00:01:21,230
et pidev korda g (x)

33
00:01:21,230 --> 00:01:23,190
iga x suurem kui x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Aga ei karda kaugusel ametlik definitsioon.

35
00:01:25,290 --> 00:01:28,020
Mida see tegelikult tähendab vähem teoreetiline mõttes?

36
00:01:28,020 --> 00:01:30,580
Noh, see on põhimõtteliselt nii, et analüüsida

37
00:01:30,580 --> 00:01:33,580
kui kiiresti programmi Runtime kasvab asümptootiliselt.

38
00:01:33,580 --> 00:01:37,170
See tähendab, et kui suurust oma sisendid suurendab suunas lõpmatus,

39
00:01:37,170 --> 00:01:41,390
Ütle, et sa sorteerimine massiivi suurus 1000 võrreldes massiivi suurus 10.

40
00:01:41,390 --> 00:01:44,950
Kuidas Runtime oma programmi kasvama?

41
00:01:44,950 --> 00:01:47,390
Oletagem näiteks, loendades tähemärki

42
00:01:47,390 --> 00:01:49,350
aastal string lihtsaim viis

43
00:01:49,350 --> 00:01:51,620
 jalgsi läbi terve rea

44
00:01:51,620 --> 00:01:54,790
täht-täht ja lisades 1 kuni loendur iga märk.

45
00:01:55,700 --> 00:01:58,420
See algoritm on öelnud, et sõidetud lineaarne aeg

46
00:01:58,420 --> 00:02:00,460
seoses märkide arvu,

47
00:02:00,460 --> 00:02:02,670
"N" string.

48
00:02:02,670 --> 00:02:04,910
Ühesõnaga, see jookseb O (n).

49
00:02:05,570 --> 00:02:07,290
Miks see nii on?

50
00:02:07,290 --> 00:02:09,539
Noh, kes seda meetodit kasutavad, vajalik aeg

51
00:02:09,539 --> 00:02:11,300
läbida kogu string

52
00:02:11,300 --> 00:02:13,920
on võrdeline arvu märke.

53
00:02:13,920 --> 00:02:16,480
Counting märkide arvu 20-märgijada

54
00:02:16,480 --> 00:02:18,580
see aega võtab kaks korda nii kaua kui vaja

55
00:02:18,580 --> 00:02:20,330
lugema märkide 10-märgijada,

56
00:02:20,330 --> 00:02:23,000
sest sa pead vaatama kõik märgid

57
00:02:23,000 --> 00:02:25,740
ja iga märk võtab sama palju aega vaadata.

58
00:02:25,740 --> 00:02:28,050
Nagu te suurendada arvu märke,

59
00:02:28,050 --> 00:02:30,950
Runtime kasvab lineaarselt sisend pikkus.

60
00:02:30,950 --> 00:02:33,500
>> Nüüd kujutage ette, kui sa otsustad, et lineaarne aeg,

61
00:02:33,500 --> 00:02:36,390
O (n), lihtsalt ei olnud piisavalt kiire Teie jaoks?

62
00:02:36,390 --> 00:02:38,750
Võib-olla olete ladustamiseks tohutu stringid,

63
00:02:38,750 --> 00:02:40,450
ja sa ei saa endale rohkem aega, mis kulub

64
00:02:40,450 --> 00:02:44,000
läbida kõik oma omadustelt lugedes ühe poolt-üks.

65
00:02:44,000 --> 00:02:46,650
Niisiis, sa otsustad proovida midagi muud.

66
00:02:46,650 --> 00:02:49,270
Mis siis, kui juhtuks juba salvestada mitu sümbolit

67
00:02:49,270 --> 00:02:52,690
aastal string, ütleme, muutuja nimega "len"

68
00:02:52,690 --> 00:02:54,210
varakult programmi

69
00:02:54,210 --> 00:02:57,800
enne kui isegi salvestatud kõige esimene märk teie string?

70
00:02:57,800 --> 00:02:59,980
Siis kõik soovid on teha nüüd välja selgitada stringi pikkus,

71
00:02:59,980 --> 00:03:02,570
on vaadata, mida muutuja väärtus on.

72
00:03:02,570 --> 00:03:05,530
Sa ei pea vaatama string ise üldse,

73
00:03:05,530 --> 00:03:08,160
ja pääseda väärtus muutuja nagu len peetakse

74
00:03:08,160 --> 00:03:11,100
asümptootiliselt pidevalt aega operatsiooni

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

76
00:03:13,070 --> 00:03:17,110
Miks see nii on? Noh, mäletad, mida asümptootilisest keerukus tähendab.

77
00:03:17,110 --> 00:03:19,100
Kuidas Runtime muutunud suurus

78
00:03:19,100 --> 00:03:21,400
oma sisendid kasvab?

79
00:03:21,400 --> 00:03:24,630
>> Ütle, et sa üritad saada tähemärkide arv suurem stringi.

80
00:03:24,630 --> 00:03:26,960
Noh, see pole oluline, kui suur teete stringi,

81
00:03:26,960 --> 00:03:28,690
isegi miljoni tähemärki pikk,

82
00:03:28,690 --> 00:03:31,150
kõik soovid on teha, et leida jada pikkusest selline lähenemine,

83
00:03:31,150 --> 00:03:33,790
on lugeda läbi muutuja len,

84
00:03:33,790 --> 00:03:35,440
mis sa juba teinud.

85
00:03:35,440 --> 00:03:38,200
Sisend pikkus, see, stringi pikkusena te üritate leida,

86
00:03:38,200 --> 00:03:41,510
ei mõjuta üldse, kui kiiresti teie programm töötab.

87
00:03:41,510 --> 00:03:44,550
See osa teie programmi läheks sama kiiresti edasi ühe märgijada

88
00:03:44,550 --> 00:03:46,170
ja tuhande märgijada,

89
00:03:46,170 --> 00:03:49,140
ja sellepärast see programm oleks edaspidi töötab pidevalt aega

90
00:03:49,140 --> 00:03:51,520
suhtes sisend suurus.

91
00:03:51,520 --> 00:03:53,920
>> Muidugi, seal on puudus.

92
00:03:53,920 --> 00:03:55,710
Sa veedad pildi mälu arvutis

93
00:03:55,710 --> 00:03:57,380
ladustamiseks muutuja

94
00:03:57,380 --> 00:03:59,270
ja lisaaeg kulub teil

95
00:03:59,270 --> 00:04:01,490
teha tegelikku salvestusmahtu muutuja,

96
00:04:01,490 --> 00:04:03,390
kuid küsimus on endiselt jõus,

97
00:04:03,390 --> 00:04:05,060
teada saada, kui kaua teie string oli

98
00:04:05,060 --> 00:04:07,600
ei sõltu stringi pikkusena üldse.

99
00:04:07,600 --> 00:04:10,720
Niisiis, see jookseb O (1) või pidevalt aega.

100
00:04:10,720 --> 00:04:13,070
See kindlasti ei tähenda

101
00:04:13,070 --> 00:04:15,610
et sinu kood töötab 1 aste,

102
00:04:15,610 --> 00:04:17,470
Aga ükskõik kui palju samme on,

103
00:04:17,470 --> 00:04:20,019
kui see ei muutu suurusest sisendid,

104
00:04:20,019 --> 00:04:23,420
see on ikka asümptootiliselt konstant, mis me esindame kui O (1).

105
00:04:23,420 --> 00:04:25,120
>> Nagu näete ilmselt arvan,

106
00:04:25,120 --> 00:04:27,940
seal on palju eri suur O runtimes mõõta algoritme.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmid on asümptootiliselt aeglasem kui O (n) algoritme.

108
00:04:32,980 --> 00:04:35,910
See tähendab, et kui mitu elementi (n) kasvab,

109
00:04:35,910 --> 00:04:39,280
lõpuks O (n) ² algoritme võtab rohkem aega

110
00:04:39,280 --> 00:04:41,000
kui O (n) algoritme joosta.

111
00:04:41,000 --> 00:04:43,960
See ei tähenda, O (n) algoritme alati kulgema kiiremini

112
00:04:43,960 --> 00:04:46,410
kui O (n) ² algoritme, isegi samas keskkonnas,

113
00:04:46,410 --> 00:04:48,080
sama riistvara.

114
00:04:48,080 --> 00:04:50,180
Võib-olla väikeste sisend suurused,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritm võib tegelikult töötavad kiiremini,

116
00:04:52,900 --> 00:04:55,450
kuid lõpuks, nagu sisend suurus kasvab

117
00:04:55,450 --> 00:04:58,760
suunas lõpmatusse, O (n) ² algoritmi käitusaja

118
00:04:58,760 --> 00:05:02,000
lõpuks Eclipse Runtime O (n) algoritmi.

119
00:05:02,000 --> 00:05:04,230
Nagu iga ruutkeskmised matemaatiline funktsioon

120
00:05:04,230 --> 00:05:06,510
 lõpuks mööduda mis tahes lineaarfunktsioonina

121
00:05:06,510 --> 00:05:09,200
ükskõik kui palju edumaa lineaarfunktsioon hakkab liikuma.

122
00:05:10,010 --> 00:05:12,000
Kui töötate koos suurte andmemahtude,

123
00:05:12,000 --> 00:05:15,510
algoritmide O (n) ² aega saab tõesti lõpuks aeglustub oma programmi,

124
00:05:15,510 --> 00:05:17,770
kuid väikese panuse suurused,

125
00:05:17,770 --> 00:05:19,420
siis ilmselt ei märka.

126
00:05:19,420 --> 00:05:21,280
>> Teine asümptootilisest keerukus on

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

128
00:05:24,420 --> 00:05:26,340
Näide algoritm, mis töötab selle kiiresti

129
00:05:26,340 --> 00:05:29,060
on klassikaline binaarne otsing algoritm,

130
00:05:29,060 --> 00:05:31,850
leidmiseks element juba sorteeritud elementide loetelu.

131
00:05:31,850 --> 00:05:33,400
>> Kui te ei tea, mida Kahendotsingupuu teeb,

132
00:05:33,400 --> 00:05:35,170
Ma seletan seda teile tõesti kiiresti.

133
00:05:35,170 --> 00:05:37,020
Oletame, et te otsite number 3

134
00:05:37,020 --> 00:05:40,200
Selles valikus täisarvud.

135
00:05:40,200 --> 00:05:42,140
Vaadeldakse keskel element massiivi

136
00:05:42,140 --> 00:05:46,830
ja küsib: "Kas element Ma tahan sellest suurem võrdne või vähem kui see?"

137
00:05:46,830 --> 00:05:49,150
Kui see on võrdne, siis suur. Sa leidsid element, ja sa oled teinud.

138
00:05:49,150 --> 00:05:51,300
Kui see on suurem, siis sa tead element

139
00:05:51,300 --> 00:05:53,440
peab olema paremal pool massiiv,

140
00:05:53,440 --> 00:05:55,200
ja saab ainult vaadata, et tulevikus,

141
00:05:55,200 --> 00:05:57,690
ja kui see on väiksem, siis sa tead, see peab olema vasakul poolel.

142
00:05:57,690 --> 00:06:00,980
Seda protsessi korratakse väiksema suurusega massiiv

143
00:06:00,980 --> 00:06:02,870
kuni õige element on leitud.

144
00:06:08,080 --> 00:06:11,670
>> See võimas algoritm lõikab massiivi suurus pooleks iga operatsiooni.

145
00:06:11,670 --> 00:06:14,080
Niisiis, leida element sorditud massiivi suurus 8,

146
00:06:14,080 --> 00:06:16,170
kõige rohkem (log ₂ 8)

147
00:06:16,170 --> 00:06:18,450
või 3 nimetatud toimingute,

148
00:06:18,450 --> 00:06:22,260
kontroll keskel element, seejärel lõikamise massiivi poole on vaja,

149
00:06:22,260 --> 00:06:25,670
arvestades massiivi suurus 16 võtab (log ₂ 16)

150
00:06:25,670 --> 00:06:27,480
või .4.

151
00:06:27,480 --> 00:06:30,570
See on vaid 1 operatsiooni kahekordistunud suurus massiiv.

152
00:06:30,570 --> 00:06:32,220
Kahekordistades massiivi

153
00:06:32,220 --> 00:06:35,160
suurendab Runtime vaid 1 patakas see kood.

154
00:06:35,160 --> 00:06:37,770
Jällegi, kontroll keskel element loendis, siis jagamine.

155
00:06:37,770 --> 00:06:40,440
Niisiis, see ütles, et tegutseda logaritmiline ajal

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

157
00:06:42,440 --> 00:06:44,270
Aga oota, sa ütled,

158
00:06:44,270 --> 00:06:47,510
ei see sõltub sellest, millises nimekirjas element otsite on?

159
00:06:47,510 --> 00:06:50,090
Mis siis, kui esimene element te vaatate juhtub olema õige?

160
00:06:50,090 --> 00:06:52,040
Siis, see võtab vaid 1 toiming,

161
00:06:52,040 --> 00:06:54,310
kuitahes suur nimekiri on.

162
00:06:54,310 --> 00:06:56,310
>> Noh, et miks arvuti teadlased on rohkem mõttes

163
00:06:56,310 --> 00:06:58,770
jaoks asümptootilisest keerukust, mis kajastaks parimal juhul

164
00:06:58,770 --> 00:07:01,050
ja halvima etendused algoritm.

165
00:07:01,050 --> 00:07:03,320
Rohkem korralikult, ülemise ja alumise piire

166
00:07:03,320 --> 00:07:05,090
edasi tööaega.

167
00:07:05,090 --> 00:07:07,660
Parimal juhul jaoks Kahendotsingupuu, meie element on

168
00:07:07,660 --> 00:07:09,330
seal keskel,

169
00:07:09,330 --> 00:07:11,770
ja sa saad selle konstantse ajaga,

170
00:07:11,770 --> 00:07:14,240
kuitahes suur ülejäänud massiiv on.

171
00:07:15,360 --> 00:07:17,650
Sümbol, mida kasutatakse see on Ω.

172
00:07:17,650 --> 00:07:19,930
Niisiis, see algoritm on öelnud, et sõidetud Ω (1).

173
00:07:19,930 --> 00:07:21,990
Parimal juhul leiab element kiiresti,

174
00:07:21,990 --> 00:07:24,200
ükskõik kui suur massiiv on,

175
00:07:24,200 --> 00:07:26,050
kuid halvimal juhul

176
00:07:26,050 --> 00:07:28,690
see peab läbima (log n) jagatud kontroll

177
00:07:28,690 --> 00:07:31,030
on massiiv leida õige element.

178
00:07:31,030 --> 00:07:34,270
Halvima ülemised piirid on nimetatud suurte "O", et sa juba tead.

179
00:07:34,270 --> 00:07:38,080
Nii, see on O (log n), kuid Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Lineaarne otsing seevastu

181
00:07:40,680 --> 00:07:43,220
kus te kõndida läbi iga element massiivi

182
00:07:43,220 --> 00:07:45,170
leida üks soovite,

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

184
00:07:47,420 --> 00:07:49,430
Jällegi, esimene element, mida soovite.

185
00:07:49,430 --> 00:07:51,930
Niisiis, see ei ole oluline, kui suur massiiv on.

186
00:07:51,930 --> 00:07:54,840
Halvimal juhul on see viimase elemendi massiivist.

187
00:07:54,840 --> 00:07:58,560
Nii, teil on kõndida läbi kõik n elementi massiivi seda leida,

188
00:07:58,560 --> 00:08:02,170
nagu kui sa olid otsivad 3.

189
00:08:04,320 --> 00:08:06,030
Niisiis, see jookseb O (n) ajaga

190
00:08:06,030 --> 00:08:09,330
sest see on võrdeline elementide arvu massiivis.

191
00:08:10,800 --> 00:08:12,830
>> Veel üks sümbol, mida kasutatakse on Θ.

192
00:08:12,830 --> 00:08:15,820
Seda saab kasutada, et kirjeldada algoritme, kus on parimad ja halvimal juhul

193
00:08:15,820 --> 00:08:17,440
on samad.

194
00:08:17,440 --> 00:08:20,390
See on nii jada pikkusega algoritme me rääkisime varem.

195
00:08:20,390 --> 00:08:22,780
See tähendab, et kui me seda säilitada muutuja enne

196
00:08:22,780 --> 00:08:25,160
me salvestada string ja seda hiljem pidevalt aega.

197
00:08:25,160 --> 00:08:27,920
Ükskõik, mis number

198
00:08:27,920 --> 00:08:30,130
me salvestamine et muutuja, me peame vaatama seda.

199
00:08:33,110 --> 00:08:35,110
Parimal juhul on, vaatame seda

200
00:08:35,110 --> 00:08:37,120
ja leida stringi pikkusena.

201
00:08:37,120 --> 00:08:39,799
Nii Ω (1) või parimal juhul konstantset aega.

202
00:08:39,799 --> 00:08:41,059
Halvim on see,

203
00:08:41,059 --> 00:08:43,400
me vaatame seda ja leida stringi pikkusena.

204
00:08:43,400 --> 00:08:47,300
Nii, O (1) või pidev aja halvim.

205
00:08:47,300 --> 00:08:49,180
Niisiis, kuna parimal juhul ja halvimal juhul on sama,

206
00:08:49,180 --> 00:08:52,520
võib seda öelda töötamine Θ (1) aeg.

207
00:08:54,550 --> 00:08:57,010
>> Kokkuvõttes on meil häid võimalusi põhjus umbes koodid tõhususe

208
00:08:57,010 --> 00:09:00,110
tundmata midagi reaalse aja nad joosta,

209
00:09:00,110 --> 00:09:02,270
mis mõjutab palju välistest teguritest,

210
00:09:02,270 --> 00:09:04,190
sealhulgas erinevate riist-ja tarkvara,

211
00:09:04,190 --> 00:09:06,040
või spetsiifikat oma kood.

212
00:09:06,040 --> 00:09:08,380
Samuti võimaldab see meil Mõelge hästi järele, mis juhtub

213
00:09:08,380 --> 00:09:10,180
kui suurus sisendite suureneb.

214
00:09:10,180 --> 00:09:12,490
>> Kui näed O (n) ² algoritm,

215
00:09:12,490 --> 00:09:15,240
või veel hullem, O (2 ⁿ) algoritm,

216
00:09:15,240 --> 00:09:17,170
üks kiiremini kasvavaid liike,

217
00:09:17,170 --> 00:09:19,140
sa tõesti hakata märkama aeglustumine

218
00:09:19,140 --> 00:09:21,220
kui alustate tööd suuremate andmemahtude.

219
00:09:21,220 --> 00:09:23,590
>> See on asümptootilisest keerukus. Aitäh.