1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Vjerojatno ste čuli ljudi govore o brzom ili učinkovit algoritam

2
00:00:10,950 --> 00:00:13,090
za izvršenje svoju posebnu zadaću,

3
00:00:13,090 --> 00:00:16,110
ali što točno to znači za algoritma biti brz ili učinkovit?

4
00:00:16,110 --> 00:00:18,580
Pa, to ne govori o mjerenja u realnom vremenu,

5
00:00:18,580 --> 00:00:20,500
kao sekundi ili minuta.

6
00:00:20,500 --> 00:00:22,220
To je zato što računalo hardver

7
00:00:22,220 --> 00:00:24,260
i softvera razlikuju drastično.

8
00:00:24,260 --> 00:00:26,020
Moj program može izvoditi sporije nego tvoje,

9
00:00:26,020 --> 00:00:28,000
jer sam to trčanje na starijem računalu,

10
00:00:28,000 --> 00:00:30,110
ili zato što sam se dogoditi da se igraju online video igre

11
00:00:30,110 --> 00:00:32,670
u isto vrijeme, što je krdo svinja sve moje memorije,

12
00:00:32,670 --> 00:00:35,400
ili sam možda trčanje moj program kroz različite softver

13
00:00:35,400 --> 00:00:37,550
koja komunicira sa strojem drugačije na niskoj razini.

14
00:00:37,550 --> 00:00:39,650
To je kao da uspoređujete jabuke i naranče.

15
00:00:39,650 --> 00:00:41,940
Samo zato što mi je sporije računalo traje duže

16
00:00:41,940 --> 00:00:43,410
od tvoje vratiti odgovor

17
00:00:43,410 --> 00:00:45,510
ne znači da imate učinkovitiji algoritam.

18
00:00:45,510 --> 00:00:48,830
>> Dakle, budući da ne mogu izravno usporediti runtimes programa

19
00:00:48,830 --> 00:00:50,140
u sekundi ili minuta,

20
00:00:50,140 --> 00:00:52,310
Kako ćemo usporediti dvije različite algoritme

21
00:00:52,310 --> 00:00:55,030
bez obzira na njihovu hardvera ili softvera okoliš?

22
00:00:55,030 --> 00:00:58,000
Za stvaranje ravnomjernije način mjerenja algoritamski učinkovitost,

23
00:00:58,000 --> 00:01:00,360
računalni znanstvenici i matematičari su izmislili

24
00:01:00,360 --> 00:01:03,830
pojmovi za mjerenje asimptotska složenost programa

25
00:01:03,830 --> 00:01:06,110
i zapis pod nazivom 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
za opisivanje to.

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

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

29
00:01:13,390 --> 00:01:15,140
ako postoji neki (x) vrijednost, x ₀ i

30
00:01:15,140 --> 00:01:17,630
neki konstanta, C, za koje

31
00:01:17,630 --> 00:01:19,340
f (x) je manja od ili jednaka

32
00:01:19,340 --> 00:01:21,230
da je konstanta puta g (x)

33
00:01:21,230 --> 00:01:23,190
za sve x veće od x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Ali nemojte se bojati daleko od formalne definicije.

35
00:01:25,290 --> 00:01:28,020
Što to zapravo znači u manje teorijskim terminima?

36
00:01:28,020 --> 00:01:30,580
Pa, to je u osnovi način analiziranja

37
00:01:30,580 --> 00:01:33,580
kako brzo program je runtime raste asimptotski.

38
00:01:33,580 --> 00:01:37,170
To je, kao što je veličina vaše inputa povećava prema beskonačnosti,

39
00:01:37,170 --> 00:01:41,390
recimo, ti si sortiranje niz veličine 1.000 u odnosu na niz veličine 10.

40
00:01:41,390 --> 00:01:44,950
Kako izvođenja svog programa rasti?

41
00:01:44,950 --> 00:01:47,390
Na primjer, zamislite brojanja znakova

42
00:01:47,390 --> 00:01:49,350
u nizu najjednostavniji način

43
00:01:49,350 --> 00:01:51,620
 šetnjom kroz cijeli niz

44
00:01:51,620 --> 00:01:54,790
pismo-po-slovo i dodavanjem jedne na šalteru za svakog lika.

45
00:01:55,700 --> 00:01:58,420
Ovaj algoritam je rekao da se izvoditi u linearnom vremenu

46
00:01:58,420 --> 00:02:00,460
s obzirom na broj znakova,

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

48
00:02:02,670 --> 00:02:04,910
Ukratko, to radi u O (n).

49
00:02:05,570 --> 00:02:07,290
Zašto je to?

50
00:02:07,290 --> 00:02:09,539
Pa, koristeći ovaj pristup, vrijeme potrebno

51
00:02:09,539 --> 00:02:11,300
proći cijeli niz

52
00:02:11,300 --> 00:02:13,920
je proporcionalna broju znakova.

53
00:02:13,920 --> 00:02:16,480
Prebrojavanje znakova u 20-znakova

54
00:02:16,480 --> 00:02:18,580
se događa da se dva puta dok traje

55
00:02:18,580 --> 00:02:20,330
računati znakove u 10-znakova,

56
00:02:20,330 --> 00:02:23,000
jer morate pogledati svih likova

57
00:02:23,000 --> 00:02:25,740
i svaki lik uzima istu količinu vremena da pogledate.

58
00:02:25,740 --> 00:02:28,050
Kao što ste povećati broj znakova,

59
00:02:28,050 --> 00:02:30,950
runtime će povećati linearno s ulaznim duljine.

60
00:02:30,950 --> 00:02:33,500
>> Sada, zamislite, ako ste se odlučili da linearno vrijeme,

61
00:02:33,500 --> 00:02:36,390
O (n), samo nije bio dovoljno brz za vas?

62
00:02:36,390 --> 00:02:38,750
Možda ste spremanje ogromne žice,

63
00:02:38,750 --> 00:02:40,450
i ne možete priuštiti više vremena da bi se

64
00:02:40,450 --> 00:02:44,000
proći sve svoje likove računajući jedna po jedna.

65
00:02:44,000 --> 00:02:46,650
Dakle, odlučite probati nešto drugo.

66
00:02:46,650 --> 00:02:49,270
Što ako bi se dogodilo da već pohraniti broj znakova

67
00:02:49,270 --> 00:02:52,690
u nizu, recimo, u varijablu pod nazivom 'len'

68
00:02:52,690 --> 00:02:54,210
rano u programu,

69
00:02:54,210 --> 00:02:57,800
prije nego što čak i pohranjena je prvi znak u vašem nizu?

70
00:02:57,800 --> 00:02:59,980
Zatim, sve što bi morao učiniti sada da biste saznali string duljine,

71
00:02:59,980 --> 00:03:02,570
je provjeriti što je vrijednost varijable je.

72
00:03:02,570 --> 00:03:05,530
Vi ne bi trebali gledati na žici sama na sve,

73
00:03:05,530 --> 00:03:08,160
i pristupa vrijednost varijable poput Len smatra

74
00:03:08,160 --> 00:03:11,100
asimptotski konstantna vrijeme operacije,

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

76
00:03:13,070 --> 00:03:17,110
Zašto je to? Pa, sjetite se što asimptotska složenost znači.

77
00:03:17,110 --> 00:03:19,100
Kako izvođenja promjena kao veličini

78
00:03:19,100 --> 00:03:21,400
vašeg ulaza raste?

79
00:03:21,400 --> 00:03:24,630
>> Recimo da su težak da biste dobili broj znakova u većem nizu.

80
00:03:24,630 --> 00:03:26,960
Pa, to ne bi bilo važno koliko je velik možete napraviti niz,

81
00:03:26,960 --> 00:03:28,690
čak milijun znakova,

82
00:03:28,690 --> 00:03:31,150
sve što bi morao učiniti kako bi pronašli stringa dužinu s ovom pristupu,

83
00:03:31,150 --> 00:03:33,790
je očitati vrijednost varijable Len,

84
00:03:33,790 --> 00:03:35,440
koje ste već napravili.

85
00:03:35,440 --> 00:03:38,200
Ulaz duljina, to jest, duljina niza koji pokušavate pronaći,

86
00:03:38,200 --> 00:03:41,510
ne utječe na sve kako brzo vaš program radi.

87
00:03:41,510 --> 00:03:44,550
Ovaj dio svog programa će izvoditi jednako brzo na jedan znakova

88
00:03:44,550 --> 00:03:46,170
i tisuću niz znakova,

89
00:03:46,170 --> 00:03:49,140
i to je razlog zašto je ovaj program će biti upućen kao trčanje u stalnom vrijeme

90
00:03:49,140 --> 00:03:51,520
s obzirom na ulaznu veličinu.

91
00:03:51,520 --> 00:03:53,920
>> Naravno, tu je nedostatak.

92
00:03:53,920 --> 00:03:55,710
Možete potrošiti dodatni memorijski prostor na vašem računalu

93
00:03:55,710 --> 00:03:57,380
spremanje varijable

94
00:03:57,380 --> 00:03:59,270
i dodatno vrijeme da vas vodi

95
00:03:59,270 --> 00:04:01,490
učiniti stvarni pohranu varijable,

96
00:04:01,490 --> 00:04:03,390
ali poanta i dalje stoji,

97
00:04:03,390 --> 00:04:05,060
saznati koliko dugo je niz

98
00:04:05,060 --> 00:04:07,600
ne ovisi o duljini niza na sve.

99
00:04:07,600 --> 00:04:10,720
Dakle, to radi u O (1) ili stalnom vrijeme.

100
00:04:10,720 --> 00:04:13,070
To svakako ne mora značiti

101
00:04:13,070 --> 00:04:15,610
da je vaš kod radi u jednom koraku,

102
00:04:15,610 --> 00:04:17,470
ali bez obzira na to koliko koraka je,

103
00:04:17,470 --> 00:04:20,019
ako to ne mijenja s veličinom od ulaza,

104
00:04:20,019 --> 00:04:23,420
to je još uvijek asimptotski konstanta koja mi predstavljaju kao O (1).

105
00:04:23,420 --> 00:04:25,120
>> Kao što vjerojatno možete pogoditi,

106
00:04:25,120 --> 00:04:27,940
postoji mnogo različitih velike O runtimes za mjerenje algoritme sa.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmi su asimptotski sporiji od O (n) algoritmi.

108
00:04:32,980 --> 00:04:35,910
To je, kao što je broj elemenata (n) raste,

109
00:04:35,910 --> 00:04:39,280
vremenom O (n) ² algoritmi će trebati više vremena

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

111
00:04:41,000 --> 00:04:43,960
To ne znači da O (n) algoritmi uvijek trčati brže

112
00:04:43,960 --> 00:04:46,410
od O (n) ² algoritama, čak u istom okruženju,

113
00:04:46,410 --> 00:04:48,080
na istom hardveru.

114
00:04:48,080 --> 00:04:50,180
Možda za male ulaznim veličinama,

115
00:04:50,180 --> 00:04:52,900
 je O (n) ² algoritam zapravo mogli raditi brže,

116
00:04:52,900 --> 00:04:55,450
ali, na kraju, kao ulazni veličine povećava

117
00:04:55,450 --> 00:04:58,760
prema beskonačnosti, O (n) ² algoritam je runtime

118
00:04:58,760 --> 00:05:02,000
na kraju će zasjeniti runtime od O (n) algoritma.

119
00:05:02,000 --> 00:05:04,230
Baš kao i svaki kvadratni matematički funkcije

120
00:05:04,230 --> 00:05:06,510
 na kraju će prestići bilo linearnu funkciju,

121
00:05:06,510 --> 00:05:09,200
bez obzira koliko glave početi linearnu funkciju započinje.

122
00:05:10,010 --> 00:05:12,000
Ako radite s velikom količinom podataka,

123
00:05:12,000 --> 00:05:15,510
algoritmi koji se pokreću u O (n) ² vrijeme stvarno može završiti usporava svoj program,

124
00:05:15,510 --> 00:05:17,770
ali za male ulaznim veličinama,

125
00:05:17,770 --> 00:05:19,420
vjerojatno neće ni primijetiti.

126
00:05:19,420 --> 00:05:21,280
>> Drugi asimptotska složenost je,

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

128
00:05:24,420 --> 00:05:26,340
Primjer algoritma koji radi to brzo

129
00:05:26,340 --> 00:05:29,060
je klasična binarni algoritam za pretraživanje,

130
00:05:29,060 --> 00:05:31,850
za pronalaženje element u već poredani popis elemenata.

131
00:05:31,850 --> 00:05:33,400
>> Ako ne znate što binarno pretraživanje radi,

132
00:05:33,400 --> 00:05:35,170
Ja ću to objasniti za vas jako brzo.

133
00:05:35,170 --> 00:05:37,020
Recimo da ste u potrazi za brojem 3

134
00:05:37,020 --> 00:05:40,200
u tom nizu brojeva.

135
00:05:40,200 --> 00:05:42,140
To izgleda po srednjem element niza

136
00:05:42,140 --> 00:05:46,830
i pita: "Je li element Želim veći od, jednak ili manji od ovoga?"

137
00:05:46,830 --> 00:05:49,150
Ako je jednaka, onda super. Možete naći element, i gotovi ste.

138
00:05:49,150 --> 00:05:51,300
Ako je veći, onda znate element

139
00:05:51,300 --> 00:05:53,440
mora biti u desnoj strani polja,

140
00:05:53,440 --> 00:05:55,200
i možete samo pogledati kako će u budućnosti,

141
00:05:55,200 --> 00:05:57,690
a ako je manja, onda znate da mora biti na lijevoj strani.

142
00:05:57,690 --> 00:06:00,980
Ovaj proces onda se ponavlja s manjim size niz

143
00:06:00,980 --> 00:06:02,870
do točne element pronađen.

144
00:06:08,080 --> 00:06:11,670
>> Ovaj moćan algoritam smanjuje veličina polja u pola sa svake operacije.

145
00:06:11,670 --> 00:06:14,080
Dakle, kako bi pronašli element u poredani niz veličine 8,

146
00:06:14,080 --> 00:06:16,170
najviše (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
ili tri od tih operacija,

148
00:06:18,450 --> 00:06:22,260
provjere srednji element, onda rezanje niz na pola će biti potrebno,

149
00:06:22,260 --> 00:06:25,670
dok niz veličine 16 ima (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
ili četiri operacije.

151
00:06:27,480 --> 00:06:30,570
To je samo jedan više operacija za udvostručio-size array.

152
00:06:30,570 --> 00:06:32,220
Udvostručenje veličine polja

153
00:06:32,220 --> 00:06:35,160
povećava runtime samo jedan komad ovog koda.

154
00:06:35,160 --> 00:06:37,770
Opet, provjeri srednji element liste, onda cijepanje.

155
00:06:37,770 --> 00:06:40,440
Dakle, to je rekao da radi u logaritamskom vremenu,

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

157
00:06:42,440 --> 00:06:44,270
Ali čekajte, što reći,

158
00:06:44,270 --> 00:06:47,510
ne to ovisi o tome gdje se u popisu element tražite je?

159
00:06:47,510 --> 00:06:50,090
Što ako je prvi element pogledate dogoditi da bude onaj pravi?

160
00:06:50,090 --> 00:06:52,040
Zatim, to traje samo jedan rad,

161
00:06:52,040 --> 00:06:54,310
bez obzira koliko je velik je popis.

162
00:06:54,310 --> 00:06:56,310
>> Pa, to je razlog zašto računalni znanstvenici imaju više termina

163
00:06:56,310 --> 00:06:58,770
za asimptotska složenosti koji odražavaju najbolje slučaj

164
00:06:58,770 --> 00:07:01,050
i najgori slučaj nastupi algoritma.

165
00:07:01,050 --> 00:07:03,320
Još točnije, gornja i donja granica

166
00:07:03,320 --> 00:07:05,090
na izvođenja.

167
00:07:05,090 --> 00:07:07,660
U najboljem slučaju za binarno pretraživanje, naš element

168
00:07:07,660 --> 00:07:09,330
tamo u sredini,

169
00:07:09,330 --> 00:07:11,770
i što ste ga dobili u stalnom vrijeme,

170
00:07:11,770 --> 00:07:14,240
bez obzira koliko veliki ostatak niza je.

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

172
00:07:17,650 --> 00:07:19,930
Dakle, ovaj algoritam je rekao da se izvoditi u Ω (1).

173
00:07:19,930 --> 00:07:21,990
U najboljem slučaju, to nađe element brzo,

174
00:07:21,990 --> 00:07:24,200
bez obzira koliko veliki niz je,

175
00:07:24,200 --> 00:07:26,050
ali u najgorem slučaju,

176
00:07:26,050 --> 00:07:28,690
to mora obaviti (log n) Split provjere

177
00:07:28,690 --> 00:07:31,030
od niza pronaći pravu element.

178
00:07:31,030 --> 00:07:34,270
Najgori slučaj-gornje granice nazivaju se s velikom "O" koje već znate.

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

180
00:07:38,080 --> 00:07:40,680
>> Linearno pretraživanje, s druge strane,

181
00:07:40,680 --> 00:07:43,220
u kojoj ste šetnja kroz svaki element niza

182
00:07:43,220 --> 00:07:45,170
pronaći onaj koji želite,

183
00:07:45,170 --> 00:07:47,420
je u najboljem Ω (1).

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

185
00:07:49,430 --> 00:07:51,930
Dakle, to ne obzira koliko je velik polje je.

186
00:07:51,930 --> 00:07:54,840
U najgorem slučaju, to je posljednji element u polju.

187
00:07:54,840 --> 00:07:58,560
Dakle, morate proći kroz svih n elemenata u niz kako bi ga pronašli,

188
00:07:58,560 --> 00:08:02,170
kao i ako ste bili u potrazi za tri.

189
00:08:04,320 --> 00:08:06,030
Dakle, to radi u O (n) vremena

190
00:08:06,030 --> 00:08:09,330
jer to je proporcionalna broju elemenata u polju.

191
00:08:10,800 --> 00:08:12,830
>> Još jedan simbol koji se koristi je Θ.

192
00:08:12,830 --> 00:08:15,820
To se može koristiti za opisivanje algoritama gdje je najbolje i najgore slučajeve

193
00:08:15,820 --> 00:08:17,440
su isti.

194
00:08:17,440 --> 00:08:20,390
To je slučaj u string duljine algoritama razgovarali smo o tome ranije.

195
00:08:20,390 --> 00:08:22,780
To je, ako ćemo ga spremiti u varijablu prije

196
00:08:22,780 --> 00:08:25,160
mi pohraniti string i pristupiti kasnije u stalnom vrijeme.

197
00:08:25,160 --> 00:08:27,920
Bez obzira na broj

198
00:08:27,920 --> 00:08:30,130
mi smo skladištenje u tu varijablu, morat ćemo gledati na to.

199
00:08:33,110 --> 00:08:35,110
Najbolji slučaj je, mi gledamo na njega

200
00:08:35,110 --> 00:08:37,120
i naći duljinu niza.

201
00:08:37,120 --> 00:08:39,799
Dakle Ω (1) ili najbolje slučaj konstantna vrijeme.

202
00:08:39,799 --> 00:08:41,059
Najgori slučaj je,

203
00:08:41,059 --> 00:08:43,400
gledamo i pronaći duljinu niza.

204
00:08:43,400 --> 00:08:47,300
Dakle, O (1) ili konstantna vrijeme u najgorem slučaju.

205
00:08:47,300 --> 00:08:49,180
Dakle, budući najboljem slučaju i najgorih slučajeva su isti,

206
00:08:49,180 --> 00:08:52,520
to može se reći da se izvoditi u Θ (1) vremena.

207
00:08:54,550 --> 00:08:57,010
>> U sažetku, imamo dobre načine kako razloga o kodovima učinkovitosti

208
00:08:57,010 --> 00:09:00,110
ne znajući ništa o stvarnom svijetu vremena su poduzeti za pokretanje,

209
00:09:00,110 --> 00:09:02,270
koja je pogođena puno vanjskih faktora,

210
00:09:02,270 --> 00:09:04,190
uključujući različitog hardvera, softvera,

211
00:09:04,190 --> 00:09:06,040
ili specifičnosti kodu.

212
00:09:06,040 --> 00:09:08,380
Također, omogućuje nam da je razlog i tome što će se dogoditi

213
00:09:08,380 --> 00:09:10,180
kada je veličina od ulaza povećava.

214
00:09:10,180 --> 00:09:12,490
>> Ako radite u O (n) ² algoritma,

215
00:09:12,490 --> 00:09:15,240
ili još gore, O (2 ⁿ) algoritam,

216
00:09:15,240 --> 00:09:17,170
jedan od najbrže rastućih vrsta,

217
00:09:17,170 --> 00:09:19,140
stvarno ćete početi primijetiti usporavanje

218
00:09:19,140 --> 00:09:21,220
kada počnete raditi s većim količinama podataka.

219
00:09:21,220 --> 00:09:23,590
>> To je asimptotska složenost. Hvala.