1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Verjetno ste že slišali ljudi govoriti o hitro in učinkovito algoritem

2
00:00:10,950 --> 00:00:13,090
Za izvedbo svoje posebno nalogo,

3
00:00:13,090 --> 00:00:16,110
Ampak kaj točno to pomeni za algoritmu, ki se hitro in učinkovito?

4
00:00:16,110 --> 00:00:18,580
No, to ne govorimo o merjenju v realnem času,

5
00:00:18,580 --> 00:00:20,500
kot sekund ali minut.

6
00:00:20,500 --> 00:00:22,220
To je zato, ker računalniške strojne opreme

7
00:00:22,220 --> 00:00:24,260
in programske opreme, znatno razlikujejo.

8
00:00:24,260 --> 00:00:26,020
Moj program lahko teče počasneje, kot je tvoj,

9
00:00:26,020 --> 00:00:28,000
ker sem njegov tek na starejšem računalniku,

10
00:00:28,000 --> 00:00:30,110
ali zato, ker sem se zgodi, da se igrajo spletne video igre

11
00:00:30,110 --> 00:00:32,670
ob istem času, ki je Pregib vse moj spomin

12
00:00:32,670 --> 00:00:35,400
ali bi jaz vodil svoj program skozi različne programske opreme

13
00:00:35,400 --> 00:00:37,550
, ki je povezan z napravo drugače na nizki ravni.

14
00:00:37,550 --> 00:00:39,650
To je tako kot bi primerjali jabolka in pomaranče.

15
00:00:39,650 --> 00:00:41,940
Samo zato, ker moj računalnik počasnejši traja dlje

16
00:00:41,940 --> 00:00:43,410
kot tvoja vrne odgovor

17
00:00:43,410 --> 00:00:45,510
ne pomeni, da imate bolj učinkovito algoritem.

18
00:00:45,510 --> 00:00:48,830
>> Torej, ker ne moremo neposredno primerjati runtimes programov

19
00:00:48,830 --> 00:00:50,140
v sekundah ali minutah,

20
00:00:50,140 --> 00:00:52,310
kako primerjati različne algoritme 2

21
00:00:52,310 --> 00:00:55,030
ne glede na njihovo okolje strojne ali programske opreme?

22
00:00:55,030 --> 00:00:58,000
Za ustvarjanje bolj enoten način merjenja učinkovitosti algoritmično,

23
00:00:58,000 --> 00:01:00,360
računalniški znanstveniki in matematiki so oblikovale

24
00:01:00,360 --> 00:01:03,830
koncepti za merjenje asimptotični kompleksnost programa

25
00:01:03,830 --> 00:01:06,110
in zapis se imenuje "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
za opis tega.

27
00:01:08,320 --> 00:01:10,820
Formalna definicija je, da je funkcija f (x)

28
00:01:10,820 --> 00:01:13,390
deluje po nalogu g (x)

29
00:01:13,390 --> 00:01:15,140
če obstaja nekaj (x) vrednost x ₀ in

30
00:01:15,140 --> 00:01:17,630
nekateri konstanta, C, za katera

31
00:01:17,630 --> 00:01:19,340
f (x) je manjša ali enaka

32
00:01:19,340 --> 00:01:21,230
da stalno krat g (x)

33
00:01:21,230 --> 00:01:23,190
za vse x večji od x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Ampak ne boj se, proč z uradnim opredelitev.

35
00:01:25,290 --> 00:01:28,020
Kaj to dejansko pomeni v manj teoretski način?

36
00:01:28,020 --> 00:01:30,580
No, to je v bistvu način za analizo

37
00:01:30,580 --> 00:01:33,580
kako hitro raste programa runtime asimptotično.

38
00:01:33,580 --> 00:01:37,170
To je, kot je velikost vaše vnose poveča do neskončnosti,

39
00:01:37,170 --> 00:01:41,390
pravijo, da ste sortiranje paleto velikosti 1000 v primerjavi z matriko velikosti 10.

40
00:01:41,390 --> 00:01:44,950
Kako teka programu rastejo?

41
00:01:44,950 --> 00:01:47,390
Predstavljajte si, prešteje število znakov

42
00:01:47,390 --> 00:01:49,350
v nizu najenostavnejši način

43
00:01:49,350 --> 00:01:51,620
 s hojo skozi celoten niz

44
00:01:51,620 --> 00:01:54,790
Pismo, ki ga črk in dodaja 1 do števca za vsak znak.

45
00:01:55,700 --> 00:01:58,420
Ta algoritem je dejal, da deluje v linearnem času

46
00:01:58,420 --> 00:02:00,460
glede na število znakov,

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

48
00:02:02,670 --> 00:02:04,910
Skratka, ta deluje v O (n).

49
00:02:05,570 --> 00:02:07,290
Zakaj je tako?

50
00:02:07,290 --> 00:02:09,539
No, s tem pristopom, je čas, potreben

51
00:02:09,539 --> 00:02:11,300
za prečkanje celotnega niza

52
00:02:11,300 --> 00:02:13,920
je sorazmerna s številom znakov.

53
00:02:13,920 --> 00:02:16,480
Prešteje število znakov v 20-znakovni niz

54
00:02:16,480 --> 00:02:18,580
bo trajalo dvakrat dlje kot traja

55
00:02:18,580 --> 00:02:20,330
za štetje znakov v 10-znakovni niz,

56
00:02:20,330 --> 00:02:23,000
ker moraš gledati na vse znake

57
00:02:23,000 --> 00:02:25,740
in vsak lik ima enako količino časa, da pogledate.

58
00:02:25,740 --> 00:02:28,050
Ko se poveča število znakov,

59
00:02:28,050 --> 00:02:30,950
runtime bo linearno povečal z vhodno dolžino.

60
00:02:30,950 --> 00:02:33,500
>> Zdaj pa si predstavljajte, če ste se odločili, da linearni čas,

61
00:02:33,500 --> 00:02:36,390
O (n), prav tako ni bil dovolj hiter za vas?

62
00:02:36,390 --> 00:02:38,750
Morda ste shranjevanje velikih nizov,

63
00:02:38,750 --> 00:02:40,450
in si ne more privoščiti več časa, da bi potrebovali

64
00:02:40,450 --> 00:02:44,000
za prečkanje vseh njihovih znakov štetje eno-by-1.

65
00:02:44,000 --> 00:02:46,650
Torej, ste se odločili, da poskusimo nekaj drugega.

66
00:02:46,650 --> 00:02:49,270
Kaj pa, če bi se zgodi, da že shranjevanje število znakov

67
00:02:49,270 --> 00:02:52,690
v nizu, recimo, v spremenljivko, imenovano "len"

68
00:02:52,690 --> 00:02:54,210
zgodaj v programu,

69
00:02:54,210 --> 00:02:57,800
še preden se hranijo zelo prvi znak v vašem nizu?

70
00:02:57,800 --> 00:02:59,980
Potem, vsi bi si morali storiti zdaj, če želite izvedeti niz dolžine,

71
00:02:59,980 --> 00:03:02,570
preverite, kaj se je vrednost spremenljivke.

72
00:03:02,570 --> 00:03:05,530
Če ne bi bilo treba pogledati v nizu sama na vse,

73
00:03:05,530 --> 00:03:08,160
in dostopa do vrednosti spremenljivke, kot len ​​šteje

74
00:03:08,160 --> 00:03:11,100
asimptotično konstantna čas delovanja,

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

76
00:03:13,070 --> 00:03:17,110
Zakaj je tako? No, ne pozabite, kaj asimptotična kompleksnosti.

77
00:03:17,110 --> 00:03:19,100
Kako runtime spremembe glede velikosti

78
00:03:19,100 --> 00:03:21,400
od vaših vložkov raste?

79
00:03:21,400 --> 00:03:24,630
>> Povejte, da ste bili poskuša priti število znakov v večji niz.

80
00:03:24,630 --> 00:03:26,960
No, ne bi bilo pomembno, kako velik naredite niz,

81
00:03:26,960 --> 00:03:28,690
celo milijonov znakov,

82
00:03:28,690 --> 00:03:31,150
Vsi bi morali storiti, da bi našli dolžino niza, je s tem pristopom,

83
00:03:31,150 --> 00:03:33,790
je prebral vrednost spremenljivke len,

84
00:03:33,790 --> 00:03:35,440
ki jo že.

85
00:03:35,440 --> 00:03:38,200
Vhodna dolžina, to je dolžina niza, ki ga poskušate najti,

86
00:03:38,200 --> 00:03:41,510
ne vpliva na vse to, kako hitro vaš program teče.

87
00:03:41,510 --> 00:03:44,550
Ta del vašega programa naj bi potekal tako hitro na eno niz znakov

88
00:03:44,550 --> 00:03:46,170
in tisoč niz znakov,

89
00:03:46,170 --> 00:03:49,140
in da je, zakaj bi se ta program imenuje teče nenehno v času

90
00:03:49,140 --> 00:03:51,520
glede na vhodni velikosti.

91
00:03:51,520 --> 00:03:53,920
>> Seveda, tam je slaba.

92
00:03:53,920 --> 00:03:55,710
Ti porabiti dodatnega pomnilnika v računalniku

93
00:03:55,710 --> 00:03:57,380
shranjevanje spremenljivke

94
00:03:57,380 --> 00:03:59,270
in dodaten čas, da vas popelje

95
00:03:59,270 --> 00:04:01,490
narediti dejanski shranjevanje spremenljivke,

96
00:04:01,490 --> 00:04:03,390
a bistvo še vedno stoji,

97
00:04:03,390 --> 00:04:05,060
ugotovite, kako dolgo je bil niz

98
00:04:05,060 --> 00:04:07,600
ni odvisen od dolžine niza sploh.

99
00:04:07,600 --> 00:04:10,720
Torej, da teče v času O (1) ali konstantni čas.

100
00:04:10,720 --> 00:04:13,070
To pa nikakor ne pomeni nujno

101
00:04:13,070 --> 00:04:15,610
kodo, ki teče v koraku 1,

102
00:04:15,610 --> 00:04:17,470
ampak ne glede na to, koliko korakov je,

103
00:04:17,470 --> 00:04:20,019
če se ne spreminja z velikostjo vložkov,

104
00:04:20,019 --> 00:04:23,420
še vedno je asimptotično konstanta, ki jih zastopamo, kot O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kot si verjetno lahko uganiti,

106
00:04:25,120 --> 00:04:27,940
obstaja veliko različnih veliki O runtimes za merjenje algoritmov s.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmi so asimptotično počasnejši od O (n) algoritmov.

108
00:04:32,980 --> 00:04:35,910
To pomeni, da je število elementov (n) raste,

109
00:04:35,910 --> 00:04:39,280
sčasoma bo O (n) ² algoritmi vzamejo več časa

110
00:04:39,280 --> 00:04:41,000
kot O (n), algoritmi za vodenje.

111
00:04:41,000 --> 00:04:43,960
To ne pomeni O (n) algoritmi vedno teči hitreje

112
00:04:43,960 --> 00:04:46,410
kot O (n) ² algoritmov, celo v istem okolju,

113
00:04:46,410 --> 00:04:48,080
na isti strojni opremi.

114
00:04:48,080 --> 00:04:50,180
Mogoče za manjše velikosti vhodnih,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritem lahko dejansko delajo hitreje,

116
00:04:52,900 --> 00:04:55,450
ampak na koncu, kot vhodni velikosti povečuje

117
00:04:55,450 --> 00:04:58,760
proti neskončnosti, je O (n) ² algoritma runtime

118
00:04:58,760 --> 00:05:02,000
bo sčasoma mrk teka O (n) algoritem.

119
00:05:02,000 --> 00:05:04,230
Tako kot vsako kvadratno matematične funkcije

120
00:05:04,230 --> 00:05:06,510
 bo na koncu prehitel vse linearno funkcijo,

121
00:05:06,510 --> 00:05:09,200
ne glede na to, koliko glav začetek linearno funkcijo se začne s.

122
00:05:10,010 --> 00:05:12,000
Če delate z velikimi količinami podatkov,

123
00:05:12,000 --> 00:05:15,510
algoritmi, ki se izvajajo v času O (n) ² čas res lahko končala upočasnjuje vaš program,

124
00:05:15,510 --> 00:05:17,770
ampak za manjše številke vnosa,

125
00:05:17,770 --> 00:05:19,420
verjetno ne boste niti opazili.

126
00:05:19,420 --> 00:05:21,280
>> Druga asimptotični kompleksnost,

127
00:05:21,280 --> 00:05:24,420
logaritemski čas O (log n).

128
00:05:24,420 --> 00:05:26,340
Primer algoritma, ki teče tako hitro

129
00:05:26,340 --> 00:05:29,060
Gre za klasično binarno iskanje algoritem,

130
00:05:29,060 --> 00:05:31,850
za iskanje elementa v že izločen seznam elementov.

131
00:05:31,850 --> 00:05:33,400
>> Če ne veste, kaj binarno iskanje ne,

132
00:05:33,400 --> 00:05:35,170
Bom razložil za vas zelo hitro.

133
00:05:35,170 --> 00:05:37,020
Recimo, da iščete številko 3

134
00:05:37,020 --> 00:05:40,200
V tem nizom števil.

135
00:05:40,200 --> 00:05:42,140
Zdi na srednji element matrike

136
00:05:42,140 --> 00:05:46,830
in vpraša: "Ali je element želim več, enako ali manj kot to?"

137
00:05:46,830 --> 00:05:49,150
Če je enaka, potem pa super. Si našel element, in ste končali.

138
00:05:49,150 --> 00:05:51,300
Če je večja, potem veste element

139
00:05:51,300 --> 00:05:53,440
mora biti na desni strani matrike,

140
00:05:53,440 --> 00:05:55,200
in lahko si samo poglej, da tudi v prihodnje,

141
00:05:55,200 --> 00:05:57,690
in če je manjša, potem veste, da mora biti na levi strani.

142
00:05:57,690 --> 00:06:00,980
Ta postopek se nato ponovi z manjšo velikosti matrike

143
00:06:00,980 --> 00:06:02,870
dokler se ne najde pravi element.

144
00:06:08,080 --> 00:06:11,670
>> Ta zmogljiv algoritem odreže velikost polja na pol, z vsako operacijo.

145
00:06:11,670 --> 00:06:14,080
Torej, da bi našli element v matriki razvrščeni po velikosti 8,

146
00:06:14,080 --> 00:06:16,170
največ (log ₂ 8)

147
00:06:16,170 --> 00:06:18,450
ali 3 od teh operacij

148
00:06:18,450 --> 00:06:22,260
preverjanje srednji element, nato pa prerezala na pol matriko bo potrebno,

149
00:06:22,260 --> 00:06:25,670
ker je matrika velikosti 16 potrebno (log ₂ 16)

150
00:06:25,670 --> 00:06:27,480
4 ali postopki.

151
00:06:27,480 --> 00:06:30,570
To je samo še 1 operacija za podvojila velikosti matrike.

152
00:06:30,570 --> 00:06:32,220
Podvojitvijo matrike

153
00:06:32,220 --> 00:06:35,160
poveča čas delovanja le za 1 kos te kode.

154
00:06:35,160 --> 00:06:37,770
Spet preverjanje srednji element na seznamu, nato pa pokati.

155
00:06:37,770 --> 00:06:40,440
Torej, je dejal, da deluje v logaritemski času,

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

157
00:06:42,440 --> 00:06:44,270
Toda počakaj, praviš,

158
00:06:44,270 --> 00:06:47,510
ni to odvisno od tega, kje na seznamu element iščeš to?

159
00:06:47,510 --> 00:06:50,090
Kaj pa, če se prvi element gledate zgodi, da je pravi?

160
00:06:50,090 --> 00:06:52,040
Potem je samo 1 postopek,

161
00:06:52,040 --> 00:06:54,310
ne glede na to, kako velik je seznam.

162
00:06:54,310 --> 00:06:56,310
>> No, to je zato računalniški znanstveniki imajo več izrazov

163
00:06:56,310 --> 00:06:58,770
Za asimptotične kompleksnosti, ki odražajo najboljšem primeru

164
00:06:58,770 --> 00:07:01,050
in najslabši nastopi algoritmom.

165
00:07:01,050 --> 00:07:03,320
Bolj pravilno, zgornja in spodnja meja

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

167
00:07:05,090 --> 00:07:07,660
V najboljšem primeru za binarnega iskanja, naš element

168
00:07:07,660 --> 00:07:09,330
tam v sredini,

169
00:07:09,330 --> 00:07:11,770
in ga dobil v stalnem času,

170
00:07:11,770 --> 00:07:14,240
ne glede na to, kako velik je preostanek niza je.

171
00:07:15,360 --> 00:07:17,650
Znak za to je Ω.

172
00:07:17,650 --> 00:07:19,930
Torej, ta algoritem je dejal, da delujejo v Ω (1).

173
00:07:19,930 --> 00:07:21,990
V najboljšem primeru se ugotovi, da je element, hitro,

174
00:07:21,990 --> 00:07:24,200
ne glede na to, kako velik je matrika,

175
00:07:24,200 --> 00:07:26,050
ampak v najslabšem primeru,

176
00:07:26,050 --> 00:07:28,690
mora izpolnjevati (log n) po delih preglede

177
00:07:28,690 --> 00:07:31,030
v matriki najti pravo element.

178
00:07:31,030 --> 00:07:34,270
Najslabšem primeru višje igrišča so navedene z velikim "O", ki ga že poznamo.

179
00:07:34,270 --> 00:07:38,080
Torej, to je O (log n), vendar Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Linearno iskanje, nasprotno,

181
00:07:40,680 --> 00:07:43,220
, v kateri hodite po vsakem elementu matrike

182
00:07:43,220 --> 00:07:45,170
da bi našli enega, ki ga želite,

183
00:07:45,170 --> 00:07:47,420
je v najboljšem primeru Ω (1).

184
00:07:47,420 --> 00:07:49,430
Spet je prvi element želite.

185
00:07:49,430 --> 00:07:51,930
Torej, ni važno, kako velik je matrika.

186
00:07:51,930 --> 00:07:54,840
V najslabšem primeru, to je zadnji element v matriki.

187
00:07:54,840 --> 00:07:58,560
Torej, moraš hoditi po vseh n elementov v matriki, da ga najdejo,

188
00:07:58,560 --> 00:08:02,170
všeč, če ste iskali za 3.

189
00:08:04,320 --> 00:08:06,030
Torej, ta deluje v O (n) časa

190
00:08:06,030 --> 00:08:09,330
ker je sorazmeren s številom elementov v matriki.

191
00:08:10,800 --> 00:08:12,830
>> Ena bolj uporabljajo simbol je Θ.

192
00:08:12,830 --> 00:08:15,820
To se lahko uporablja za opis algoritmov, kjer je najboljši in najslabši zabojev

193
00:08:15,820 --> 00:08:17,440
so enaki.

194
00:08:17,440 --> 00:08:20,390
Tako je na primer v niz dolžine algoritmov smo govorili o prej.

195
00:08:20,390 --> 00:08:22,780
To je, če jo shranite v spremenljivko, preden

196
00:08:22,780 --> 00:08:25,160
hranimo niz in dostop kasneje v stalnem času.

197
00:08:25,160 --> 00:08:27,920
Ne glede na to, kam

198
00:08:27,920 --> 00:08:30,130
smo skladiščenje v te spremenljivke, bomo morali pogledati.

199
00:08:33,110 --> 00:08:35,110
Najboljši primer je, gledamo na to

200
00:08:35,110 --> 00:08:37,120
in našli dolžino niza.

201
00:08:37,120 --> 00:08:39,799
Torej Ω (1) ali najboljšem primeru konstanten čas.

202
00:08:39,799 --> 00:08:41,059
V najslabšem primeru je,

203
00:08:41,059 --> 00:08:43,400
gledamo na to in najdite dolžino niza.

204
00:08:43,400 --> 00:08:47,300
Torej, O (1) ali konstantni čas, v najslabšem primeru.

205
00:08:47,300 --> 00:08:49,180
Torej, ker najboljšem primeru in najhujših primerih enaka,

206
00:08:49,180 --> 00:08:52,520
to lahko rečemo, da delujejo v Θ (1) časa.

207
00:08:54,550 --> 00:08:57,010
>> Skratka, imamo dobre možnosti, da zato o učinkovitosti kode

208
00:08:57,010 --> 00:09:00,110
ne da bi vedel ničesar o resničnem času, ko začnejo teči,

209
00:09:00,110 --> 00:09:02,270
ki jo je prizadela veliko zunanjih dejavnikov,

210
00:09:02,270 --> 00:09:04,190
vključno z različno strojno opremo, programsko opremo,

211
00:09:04,190 --> 00:09:06,040
ali posebnosti kode.

212
00:09:06,040 --> 00:09:08,380
Prav tako nam omogoča, da dobro razmislite o tem, kaj se bo zgodilo

213
00:09:08,380 --> 00:09:10,180
ko je obseg vhodnih povečuje.

214
00:09:10,180 --> 00:09:12,490
>> Če delate v O (n) ² algoritem,

215
00:09:12,490 --> 00:09:15,240
ali še huje, O (2 ⁿ) algoritem,

216
00:09:15,240 --> 00:09:17,170
ena izmed najhitreje rastočih vrst,

217
00:09:17,170 --> 00:09:19,140
boste resnično začeli opažati upočasnitev

218
00:09:19,140 --> 00:09:21,220
ko začnete delati z večjimi količinami podatkov.

219
00:09:21,220 --> 00:09:23,590
>> To je asimptotični kompleksnosti. Hvala.