1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Pravdepodobne ste počuli ľudia hovoria o rýchly, alebo efektívny algoritmus

2
00:00:10,950 --> 00:00:13,090
pre vykonávanie váš konkrétnu úlohu,

3
00:00:13,090 --> 00:00:16,110
ale čo presne to znamená pre algoritmus, ktorý bude rýchlo, alebo efektívny?

4
00:00:16,110 --> 00:00:18,580
No, to nehovorím o meranie v reálnom čase,

5
00:00:18,580 --> 00:00:20,500
ako sekundách alebo minútach.

6
00:00:20,500 --> 00:00:22,220
To je preto, že počítačový hardvér

7
00:00:22,220 --> 00:00:24,260
a softvér radikálne líšiť.

8
00:00:24,260 --> 00:00:26,020
Môj program môže bežať pomalšie ako vy,

9
00:00:26,020 --> 00:00:28,000
pretože som beží to na staršom počítači,

10
00:00:28,000 --> 00:00:30,110
alebo preto, že som sa náhodou hrať online videohru

11
00:00:30,110 --> 00:00:32,670
súčasne dobe, ktorá je hogging všetky moje pamäti,

12
00:00:32,670 --> 00:00:35,400
alebo by som mohol byť spustený môj program prostredníctvom rôznych softvér

13
00:00:35,400 --> 00:00:37,550
ktorý komunikuje so strojom inak na nízkej úrovni.

14
00:00:37,550 --> 00:00:39,650
Je to ako porovnávať jablká s hruškami.

15
00:00:39,650 --> 00:00:41,940
Len preto, že môj pomalší počítač trvá dlhšie

16
00:00:41,940 --> 00:00:43,410
ako vaše vrátiť odpoveď

17
00:00:43,410 --> 00:00:45,510
neznamená, že budete mať viac efektívny algoritmus.

18
00:00:45,510 --> 00:00:48,830
>> Takže, pretože nemôžeme priamo porovnávať runtime programov

19
00:00:48,830 --> 00:00:50,140
v sekundách alebo minútach,

20
00:00:50,140 --> 00:00:52,310
ako sme tieto 2 rôzne algoritmy

21
00:00:52,310 --> 00:00:55,030
bez ohľadu na ich hardvérové ​​alebo softvérové ​​prostredie?

22
00:00:55,030 --> 00:00:58,000
Ak chcete vytvoriť viac jednotný spôsob merania efektivity algoritmov,

23
00:00:58,000 --> 00:01:00,360
počítačové vedci a matematici vymysleli

24
00:01:00,360 --> 00:01:03,830
koncepty pre meranie asymptotickej zložitosť programu

25
00:01:03,830 --> 00:01:06,110
a zápis názvom "Big Ohnotation"

26
00:01:06,110 --> 00:01:08,320
pre popis tohto.

27
00:01:08,320 --> 00:01:10,820
Formálne definície je, že funkcia f (x)

28
00:01:10,820 --> 00:01:13,390
beží na poradie g (x)

29
00:01:13,390 --> 00:01:15,140
či existuje nejaký (x) hodnoty, x ₀ a

30
00:01:15,140 --> 00:01:17,630
nejaká konštanta, C, pre ktoré

31
00:01:17,630 --> 00:01:19,340
f (x) je menší ako alebo rovný

32
00:01:19,340 --> 00:01:21,230
že konštantné časy g (x)

33
00:01:21,230 --> 00:01:23,190
pre všetky x väčšie ako x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Ale neboj sa preč formálne definíciu.

35
00:01:25,290 --> 00:01:28,020
Čo to vlastne znamená v menej teoretických pojmoch?

36
00:01:28,020 --> 00:01:30,580
No, je to v podstate spôsob, ako analyzovať

37
00:01:30,580 --> 00:01:33,580
Ako rýchlo programu runtime rastie asymptoticky.

38
00:01:33,580 --> 00:01:37,170
To je, ako veľkosť vašich vstupov zvyšuje smerom k nekonečnu,

39
00:01:37,170 --> 00:01:41,390
povedzme, že ste triedenie poľa o veľkosti 1000 v porovnaní s radom veľkosťou 10.

40
00:01:41,390 --> 00:01:44,950
Ako runtime vášho programu rast?

41
00:01:44,950 --> 00:01:47,390
Predstavte si napríklad, počítanie počtu znakov

42
00:01:47,390 --> 00:01:49,350
v reťazci najjednoduchší spôsob, ako

43
00:01:49,350 --> 00:01:51,620
 pešo cez celý reťazec

44
00:01:51,620 --> 00:01:54,790
Letter podľa písmen a pridaním 1 k prepážke pre každého znaku.

45
00:01:55,700 --> 00:01:58,420
Tento algoritmus je povedal, aby spustenie v lineárnom čase

46
00:01:58,420 --> 00:02:00,460
s ohľadom na počet znakov,

47
00:02:00,460 --> 00:02:02,670
"N" v reťazci.

48
00:02:02,670 --> 00:02:04,910
Stručne povedané, to beží v O (n).

49
00:02:05,570 --> 00:02:07,290
Prečo to je?

50
00:02:07,290 --> 00:02:09,539
No, použitie tohto prístupu, čas potrebný

51
00:02:09,539 --> 00:02:11,300
prejsť celý reťazec

52
00:02:11,300 --> 00:02:13,920
je úmerná počtu znakov.

53
00:02:13,920 --> 00:02:16,480
Počítanie znakov v 20-znakový reťazec

54
00:02:16,480 --> 00:02:18,580
bude trvať dvakrát tak dlho, ako bude potrebné

55
00:02:18,580 --> 00:02:20,330
počítať znaky v 10-znakový reťazec,

56
00:02:20,330 --> 00:02:23,000
pretože sa musíte pozrieť na všetky znaky

57
00:02:23,000 --> 00:02:25,740
a každá postava má rovnaké množstvo času pozrieť sa na.

58
00:02:25,740 --> 00:02:28,050
Ako zvýšiť počet znakov,

59
00:02:28,050 --> 00:02:30,950
runtime zvýši lineárne s dĺžkou vstupného.

60
00:02:30,950 --> 00:02:33,500
>> Teraz si predstavte, keď sa rozhodnete, že lineárny čas,

61
00:02:33,500 --> 00:02:36,390
O (n), jednoducho nie je dostatočne rýchly pre vás?

62
00:02:36,390 --> 00:02:38,750
Možno ste ukladanie obrovské reťazca,

63
00:02:38,750 --> 00:02:40,450
a môžete si dovoliť čas navyše, že by trvať

64
00:02:40,450 --> 00:02:44,000
prejsť všetky ich znaky počítanie jeden po-one.

65
00:02:44,000 --> 00:02:46,650
Takže, ste sa rozhodli skúsiť niečo iné.

66
00:02:46,650 --> 00:02:49,270
Čo keď sa stane už uložiť počet znakov

67
00:02:49,270 --> 00:02:52,690
v reťazci, teda v premennej s názvom "ľan"

68
00:02:52,690 --> 00:02:54,210
na začiatku programu,

69
00:02:54,210 --> 00:02:57,800
ešte predtým, než uloží úplne prvý znak vo vašom reťazci?

70
00:02:57,800 --> 00:02:59,980
Potom všetko, čo budem musieť urobiť, zistiť dĺžku reťazca,

71
00:02:59,980 --> 00:03:02,570
je zistiť, čo hodnota premennej je.

72
00:03:02,570 --> 00:03:05,530
Nemala by ste sa pozrieť na reťazec sám vôbec,

73
00:03:05,530 --> 00:03:08,160
a prístup k hodnotu premennej ako ľan sa považuje

74
00:03:08,160 --> 00:03:11,100
asymptoticky konštantný čas operácie,

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

76
00:03:13,070 --> 00:03:17,110
Prečo to je? No, spomenúť si, čo asymptotickej zložitosť znamená.

77
00:03:17,110 --> 00:03:19,100
Ako runtime zmena, ako je veľkosť

78
00:03:19,100 --> 00:03:21,400
z vašich vstupov rastie?

79
00:03:21,400 --> 00:03:24,630
>> Povedzme, že ste sa snažili dostať počet znakov v reťazci väčší.

80
00:03:24,630 --> 00:03:26,960
No, to by nebolo jedno, aký veľký urobíte reťazec,

81
00:03:26,960 --> 00:03:28,690
dokonca miliónov znakov,

82
00:03:28,690 --> 00:03:31,150
všetko, čo budem musieť urobiť, nájsť aktívnu dĺžku struny s týmto prístupom,

83
00:03:31,150 --> 00:03:33,790
je prečítať hodnotu premennej ľan,

84
00:03:33,790 --> 00:03:35,440
ktoré ste už vykonaná.

85
00:03:35,440 --> 00:03:38,200
Vstupné dĺžka, to znamená, že dĺžka reťazca, ktorý sa snažíte nájsť,

86
00:03:38,200 --> 00:03:41,510
nemá vplyv vôbec, ako rýchlo váš program beží.

87
00:03:41,510 --> 00:03:44,550
Táto časť programu by bežať rovnako rýchlo na jeden reťazec znakov

88
00:03:44,550 --> 00:03:46,170
a tisíc znakový reťazec,

89
00:03:46,170 --> 00:03:49,140
a to je dôvod, prečo by tento program byť odvolával sa na ako beh v konštantnom čase

90
00:03:49,140 --> 00:03:51,520
s ohľadom na vstupné veľkosť.

91
00:03:51,520 --> 00:03:53,920
>> Samozrejme, je tu nevýhodu.

92
00:03:53,920 --> 00:03:55,710
Môžete stráviť ďalšie pamäť v počítači

93
00:03:55,710 --> 00:03:57,380
ukladanie premenné

94
00:03:57,380 --> 00:03:59,270
a viac času to bude trvať

95
00:03:59,270 --> 00:04:01,490
robiť skutočné uloženie premenné,

96
00:04:01,490 --> 00:04:03,390
ale bod stále stojí,

97
00:04:03,390 --> 00:04:05,060
zistiť, ako dlho bude reťazec bol

98
00:04:05,060 --> 00:04:07,600
nezávisí na dĺžke reťazca vôbec.

99
00:04:07,600 --> 00:04:10,720
Takže, to beží v O (1), alebo konštantné čas.

100
00:04:10,720 --> 00:04:13,070
To rozhodne nemusí znamenať,

101
00:04:13,070 --> 00:04:15,610
že váš kód beží v 1 kroku,

102
00:04:15,610 --> 00:04:17,470
ale bez ohľadu na to, koľko krokov je to,

103
00:04:17,470 --> 00:04:20,019
ak nemenia s veľkosťou vstupov,

104
00:04:20,019 --> 00:04:23,420
je to stále asymptoticky konštanta, ktorá sa predstavuje ako O (1).

105
00:04:23,420 --> 00:04:25,120
>> Ako asi tušíte,

106
00:04:25,120 --> 00:04:27,940
existuje veľa rôznych veľkých O behové merať algoritmy s

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmy sú asymptoticky pomalší ako algoritmy O (n).

108
00:04:32,980 --> 00:04:35,910
To znamená, že aj počet prvkov (n) rastie,

109
00:04:35,910 --> 00:04:39,280
nakoniec O (n) ² algoritmy budú mať viac času

110
00:04:39,280 --> 00:04:41,000
ako O (n) algoritmy pre spustenie.

111
00:04:41,000 --> 00:04:43,960
To neznamená, O (n) algoritmy vždy bežať rýchlejšie

112
00:04:43,960 --> 00:04:46,410
ako O (N) ² algoritmov, a to aj v rovnakom prostredí,

113
00:04:46,410 --> 00:04:48,080
na rovnakom hardvéri.

114
00:04:48,080 --> 00:04:50,180
Možno, že pre malé vstupné veľkosti,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmus v skutočnosti môže pracovať rýchlejšie,

116
00:04:52,900 --> 00:04:55,450
ale, nakoniec, ako vstupné veľkosti zvyšuje

117
00:04:55,450 --> 00:04:58,760
k nekonečnu, O (n) ² algoritmu runtime

118
00:04:58,760 --> 00:05:02,000
nakoniec zatieniť runtime O (n) algoritmu.

119
00:05:02,000 --> 00:05:04,230
Rovnako ako nejaké kvadratickej matematické funkcie

120
00:05:04,230 --> 00:05:06,510
 nakoniec predbehnú všetky lineárne funkcie,

121
00:05:06,510 --> 00:05:09,200
bez ohľadu na to, koľko z hlavy kto lineárne funkciu začína s

122
00:05:10,010 --> 00:05:12,000
Ak pracujete s veľkým množstvom dát,

123
00:05:12,000 --> 00:05:15,510
algoritmy, ktoré pracujú v O (n) ² doba sa môže naozaj skončiť spomalenie programu,

124
00:05:15,510 --> 00:05:17,770
ale pre malé vstupné veľkosti,

125
00:05:17,770 --> 00:05:19,420
pravdepodobne ani nevšimnete.

126
00:05:19,420 --> 00:05:21,280
>> Ďalšie asymptotickej zložitosť je,

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

128
00:05:24,420 --> 00:05:26,340
Príkladom algoritmu, ktorý beží tak rýchlo

129
00:05:26,340 --> 00:05:29,060
je klasický binárny vyhľadávací algoritmus,

130
00:05:29,060 --> 00:05:31,850
pre zistenie prvku v už triedenom zozname prvkov.

131
00:05:31,850 --> 00:05:33,400
>> Ak neviete, čo binárne vyhľadávacie robí,

132
00:05:33,400 --> 00:05:35,170
Vysvetlím ti to pre teba naozaj rýchlo.

133
00:05:35,170 --> 00:05:37,020
Povedzme, že hľadáte pre číslo 3

134
00:05:37,020 --> 00:05:40,200
v tomto poli celých čísel.

135
00:05:40,200 --> 00:05:42,140
Zdá sa na strednej prvku matice

136
00:05:42,140 --> 00:05:46,830
a pýta sa: "Je element chcem väčší, rovná alebo menšia ako toto?"

137
00:05:46,830 --> 00:05:49,150
Ak je to rovnaké, potom skvelé. Našli ste prvok, a máte hotovo.

138
00:05:49,150 --> 00:05:51,300
Ak je to väčšia, potom viete, že prvok

139
00:05:51,300 --> 00:05:53,440
musí byť v pravej časti poľa,

140
00:05:53,440 --> 00:05:55,200
a môžete sa pozrieť na, že v budúcnosti,

141
00:05:55,200 --> 00:05:57,690
a, ak je to menšie, potom viete, že má byť na ľavej strane.

142
00:05:57,690 --> 00:06:00,980
Tento proces sa opakuje s menšou veľkosťou poľa

143
00:06:00,980 --> 00:06:02,870
až do dosiahnutia správnej prvok nájdený.

144
00:06:08,080 --> 00:06:11,670
>> Tento výkonný algoritmus znižuje veľkosť poľa na polovicu každej operácii.

145
00:06:11,670 --> 00:06:14,080
Takže, nájsť element v triedenom poli o veľkosti 8,

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

147
00:06:16,170 --> 00:06:18,450
alebo 3 z týchto operácií,

148
00:06:18,450 --> 00:06:22,260
kontrolu strednej prvok, potom delenie poľa na polovicu bude nutné,

149
00:06:22,260 --> 00:06:25,670
vzhľadom k tomu, pole o veľkosti 16 má (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
alebo 4 operácie.

151
00:06:27,480 --> 00:06:30,570
To je len 1 viac prevádzku na dvojnásobok veľkosti poľa.

152
00:06:30,570 --> 00:06:32,220
Zdvojnásobenie veľkosti poľa

153
00:06:32,220 --> 00:06:35,160
zvyšuje runtime iba 1 kus tohto kódu.

154
00:06:35,160 --> 00:06:37,770
Opäť, kontrola prostredný prvok zoznamu, potom rozdelenie.

155
00:06:37,770 --> 00:06:40,440
Takže, je to údajne v prevádzke v logaritmickom čase,

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

157
00:06:42,440 --> 00:06:44,270
Ale počkajte, vy hovoríte,

158
00:06:44,270 --> 00:06:47,510
nie je to závisí od toho, kde v zozname, prvok, ktorý hľadáte, je?

159
00:06:47,510 --> 00:06:50,090
Čo keď prvý prvok sa pozriete na stane sa pravý?

160
00:06:50,090 --> 00:06:52,040
Potom, to trvá len 1 operáciu,

161
00:06:52,040 --> 00:06:54,310
bez ohľadu na to, aký veľký je zoznam.

162
00:06:54,310 --> 00:06:56,310
>> No, to je dôvod, prečo počítačoví odborníci majú viac pojmov

163
00:06:56,310 --> 00:06:58,770
pre asymptotickej zložitosti, ktoré odrážajú najlepšie prípad

164
00:06:58,770 --> 00:07:01,050
a najhoršie vystúpenie algoritmu.

165
00:07:01,050 --> 00:07:03,320
Viac správne, horná a dolná hranica

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

167
00:07:05,090 --> 00:07:07,660
V najlepšom prípade pre binárne vyhľadávanie, náš prvok

168
00:07:07,660 --> 00:07:09,330
priamo tam uprostred,

169
00:07:09,330 --> 00:07:11,770
a dostanete ho v konštantnom čase,

170
00:07:11,770 --> 00:07:14,240
bez ohľadu na to, aký veľký zvyšok poľa je.

171
00:07:15,360 --> 00:07:17,650
Symbol používa pre toto je Ω.

172
00:07:17,650 --> 00:07:19,930
Takže, je tento algoritmus hovorí bežať Ω (1).

173
00:07:19,930 --> 00:07:21,990
V najlepšom prípade, že nájde prvok rýchlo,

174
00:07:21,990 --> 00:07:24,200
bez ohľadu na to, aký veľký je pole,

175
00:07:24,200 --> 00:07:26,050
ale v najhoršom prípade,

176
00:07:26,050 --> 00:07:28,690
má vykonať (log n) rozštiepené kontroly

177
00:07:28,690 --> 00:07:31,030
z poľa nájsť ten správny prvok.

178
00:07:31,030 --> 00:07:34,270
Najhoršie hornej hranice sú odvolával sa na s veľkým "O", ktoré už poznáte.

179
00:07:34,270 --> 00:07:38,080
Takže, je to O (log n), ale Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Lineárne vyhľadávanie, naopak,

181
00:07:40,680 --> 00:07:43,220
, V ktorom sa prejdete každý prvok poľa

182
00:07:43,220 --> 00:07:45,170
nájsť ten, ktorý chcete,

183
00:07:45,170 --> 00:07:47,420
je v najlepšom prípade Ω (1).

184
00:07:47,420 --> 00:07:49,430
Opäť, prvý prvok, ktorý chcete.

185
00:07:49,430 --> 00:07:51,930
Takže, nezáleží na tom, aký veľký je pole.

186
00:07:51,930 --> 00:07:54,840
V najhoršom prípade, je to posledný prvok v poli.

187
00:07:54,840 --> 00:07:58,560
Takže, budete musieť prejsť všetky n prvkov v poli nájsť,

188
00:07:58,560 --> 00:08:02,170
ako keď hľadali 3.

189
00:08:04,320 --> 00:08:06,030
Takže, to beží v O (n) čas

190
00:08:06,030 --> 00:08:09,330
, Pretože je to priamo úmerná počtu prvkov v poli.

191
00:08:10,800 --> 00:08:12,830
>> A ešte jedna použitý symbol je Θ.

192
00:08:12,830 --> 00:08:15,820
To môže byť použitý k popisu algoritmov, kde je najlepšie a najhoršie prípady

193
00:08:15,820 --> 00:08:17,440
sú rovnaké.

194
00:08:17,440 --> 00:08:20,390
To je prípad v reťazci dĺžky algoritmov sme hovorili o skôr.

195
00:08:20,390 --> 00:08:22,780
To znamená, že ak uložíme ju do premennej pred

196
00:08:22,780 --> 00:08:25,160
uložíme reťazec a prístup neskôr v konštantnom čase.

197
00:08:25,160 --> 00:08:27,920
Bez ohľadu na to, aký počet

198
00:08:27,920 --> 00:08:30,130
sme skladovanie v tejto premennej, budeme sa musieť pozrieť na to.

199
00:08:33,110 --> 00:08:35,110
Najlepšia vec je, že sme sa na to pozrieť

200
00:08:35,110 --> 00:08:37,120
a nájsť dĺžku reťazca.

201
00:08:37,120 --> 00:08:39,799
Takže Ω (1) alebo best case konštantný čas.

202
00:08:39,799 --> 00:08:41,059
Najhorší prípad je,

203
00:08:41,059 --> 00:08:43,400
Pozrieme sa na to a nájsť dĺžku reťazca.

204
00:08:43,400 --> 00:08:47,300
Takže, O (1), alebo konštantné čas v najhoršom prípade.

205
00:08:47,300 --> 00:08:49,180
Takže, pretože najlepšie veci a najhoršie prípady sú rovnaké,

206
00:08:49,180 --> 00:08:52,520
Tento sa dá povedať, že beží v Θ (1), je čas.

207
00:08:54,550 --> 00:08:57,010
>> Stručne povedané, máme dobré spôsoby, ako uvažovať o účinnosti kódy

208
00:08:57,010 --> 00:09:00,110
bez toho aby vedel niečo o real-svetového času kedy prijmú bežať,

209
00:09:00,110 --> 00:09:02,270
ktorá je ovplyvnená množstvom vonkajších faktorov,

210
00:09:02,270 --> 00:09:04,190
vrátane odlišného hardvéru, softvéru,

211
00:09:04,190 --> 00:09:06,040
alebo špecifiká vášho kódu.

212
00:09:06,040 --> 00:09:08,380
Tiež, to nám umožňuje rozum, dobre o tom, čo sa stane

213
00:09:08,380 --> 00:09:10,180
kedy veľkosť vstupov zvyšuje.

214
00:09:10,180 --> 00:09:12,490
>> Ak beží v O (n) ² algoritmus,

215
00:09:12,490 --> 00:09:15,240
alebo ešte horšie, O (2 ⁿ) algoritmus,

216
00:09:15,240 --> 00:09:17,170
jeden z najrýchlejšie rastúcich typov,

217
00:09:17,170 --> 00:09:19,140
budete naozaj začnete si uvedomovať, spomalenie

218
00:09:19,140 --> 00:09:21,220
keď začnete pracovať s veľkým množstvom dát.

219
00:09:21,220 --> 00:09:23,590
>> To je asymptotickej zložitosť. Vďaka.