1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Pravděpodobně jste slyšeli lidé mluví o rychlý, nebo efektivní algoritmus

2
00:00:10,950 --> 00:00:13,090
pro provádění váš konkrétní úkol,

3
00:00:13,090 --> 00:00:16,110
ale co přesně to znamená pro algoritmus, který bude rychle, nebo účinný?

4
00:00:16,110 --> 00:00:18,580
No, to nemluvím o měření v reálném čase,

5
00:00:18,580 --> 00:00:20,500
jako sekundách nebo minutách.

6
00:00:20,500 --> 00:00:22,220
To je proto, že počítačový hardware

7
00:00:22,220 --> 00:00:24,260
a software radikálně lišit.

8
00:00:24,260 --> 00:00:26,020
Můj program může běžet pomaleji než vy,

9
00:00:26,020 --> 00:00:28,000
protože jsem běží to na starším počítači,

10
00:00:28,000 --> 00:00:30,110
nebo proto, že jsem se náhodou hrát online videohru

11
00:00:30,110 --> 00:00:32,670
současně, což je hogging všechny mé paměti,

12
00:00:32,670 --> 00:00:35,400
nebo bych mohl být spuštěn můj program prostřednictvím různých software

13
00:00:35,400 --> 00:00:37,550
který komunikuje se strojem jinak na nízké úrovni.

14
00:00:37,550 --> 00:00:39,650
Je to jako srovnávat jablka s hruškami.

15
00:00:39,650 --> 00:00:41,940
Jen proto, že můj pomalejší počítač trvá déle

16
00:00:41,940 --> 00:00:43,410
než vaše vrátit odpověď

17
00:00:43,410 --> 00:00:45,510
neznamená, že budete mít více efektivní algoritmus.

18
00:00:45,510 --> 00:00:48,830
>> Takže, protože nemůžeme přímo porovnávat runtime programů

19
00:00:48,830 --> 00:00:50,140
v sekundách nebo minutách,

20
00:00:50,140 --> 00:00:52,310
jak jsme tyto 2 různé algoritmy

21
00:00:52,310 --> 00:00:55,030
bez ohledu na jejich hardwarové nebo softwarové prostředí?

22
00:00:55,030 --> 00:00:58,000
Chcete-li vytvořit více jednotný způsob měření efektivity algoritmů,

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

24
00:01:00,360 --> 00:01:03,830
koncepty pro měření asymptotickou složitost programu

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

26
00:01:06,110 --> 00:01:08,320
pro popis tohoto.

27
00:01:08,320 --> 00:01:10,820
Formální definice je to, že funkce f (x)

28
00:01:10,820 --> 00:01:13,390
běží na pořadí g (x)

29
00:01:13,390 --> 00:01:15,140
zda existuje nějaký (x) hodnoty, x ₀ a

30
00:01:15,140 --> 00:01:17,630
nějaká konstanta, C, pro které

31
00:01:17,630 --> 00:01:19,340
f (x) je menší než nebo roven

32
00:01:19,340 --> 00:01:21,230
že konstantní časy g (x)

33
00:01:21,230 --> 00:01:23,190
pro všechny x větší než x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Ale neboj se pryč formální definici.

35
00:01:25,290 --> 00:01:28,020
Co to vlastně znamená v méně teoretických pojmech?

36
00:01:28,020 --> 00:01:30,580
No, je to v podstatě způsob, jak analyzovat

37
00:01:30,580 --> 00:01:33,580
Jak rychle programu runtime roste asymptoticky.

38
00:01:33,580 --> 00:01:37,170
To je, jak velikost vašich vstupů zvyšuje směrem k nekonečnu,

39
00:01:37,170 --> 00:01:41,390
řekněme, že jste třídění pole o velikosti 1000 ve srovnání s řadou velikostí 10.

40
00:01:41,390 --> 00:01:44,950
Jak runtime vašeho programu růst?

41
00:01:44,950 --> 00:01:47,390
Představte si například, počítání počtu znaků

42
00:01:47,390 --> 00:01:49,350
v řetězci nejjednodušší způsob, jak

43
00:01:49,350 --> 00:01:51,620
 pěšky přes celý řetězec

44
00:01:51,620 --> 00:01:54,790
Letter podle písmen a přidáním 1 k přepážce pro každého znaku.

45
00:01:55,700 --> 00:01:58,420
Tento algoritmus je řekl, aby spuštění v lineárním čase

46
00:01:58,420 --> 00:02:00,460
s ohledem na počet znaků,

47
00:02:00,460 --> 00:02:02,670
"N" v řetězci.

48
00:02:02,670 --> 00:02:04,910
Stručně řečeno, to běží v O (n).

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

50
00:02:07,290 --> 00:02:09,539
No, použití tohoto přístupu, čas potřebný

51
00:02:09,539 --> 00:02:11,300
přejít celý řetězec

52
00:02:11,300 --> 00:02:13,920
je úměrná počtu znaků.

53
00:02:13,920 --> 00:02:16,480
Počítání znaků v 20-znakový řetězec

54
00:02:16,480 --> 00:02:18,580
bude trvat dvakrát tak dlouho, jak bude potřeba

55
00:02:18,580 --> 00:02:20,330
počítat znaky v 10-znakový řetězec,

56
00:02:20,330 --> 00:02:23,000
protože se musíte podívat na všechny znaky

57
00:02:23,000 --> 00:02:25,740
a každá postava má stejné množství času podívat se na.

58
00:02:25,740 --> 00:02:28,050
Jak zvýšit počet znaků,

59
00:02:28,050 --> 00:02:30,950
runtime zvýší lineárně s délkou vstupního.

60
00:02:30,950 --> 00:02:33,500
>> Teď si představte, když se rozhodnete, že lineární čas,

61
00:02:33,500 --> 00:02:36,390
O (n), prostě není dostatečně rychlý pro vás?

62
00:02:36,390 --> 00:02:38,750
Možná jste ukládání obrovské řetězce,

63
00:02:38,750 --> 00:02:40,450
a můžete si dovolit čas navíc, že ​​by trvat

64
00:02:40,450 --> 00:02:44,000
přejít všechny jejich znaky počítání jeden po-one.

65
00:02:44,000 --> 00:02:46,650
Takže, jste se rozhodli zkusit něco jiného.

66
00:02:46,650 --> 00:02:49,270
Co když se stane již uložit počet znaků

67
00:02:49,270 --> 00:02:52,690
v řetězci, tedy v proměnné s názvem "len"

68
00:02:52,690 --> 00:02:54,210
na počátku programu,

69
00:02:54,210 --> 00:02:57,800
ještě předtím, než uloží úplně první znak ve vašem řetězci?

70
00:02:57,800 --> 00:02:59,980
Pak vše, co budu muset udělat, zjistit délku řetězce,

71
00:02:59,980 --> 00:03:02,570
je zjistit, co hodnota proměnné je.

72
00:03:02,570 --> 00:03:05,530
Neměla byste se podívat na řetězec sám vůbec,

73
00:03:05,530 --> 00:03:08,160
a přístup k hodnotu proměnné jako len se považuje

74
00:03:08,160 --> 00:03:11,100
asymptoticky konstantní čas operace,

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

76
00:03:13,070 --> 00:03:17,110
Proč to je? No, vzpomenout si, co asymptotická složitost znamená.

77
00:03:17,110 --> 00:03:19,100
Jak se runtime změna, jako je velikost

78
00:03:19,100 --> 00:03:21,400
z vašich vstupů roste?

79
00:03:21,400 --> 00:03:24,630
>> Řekněme, že jste se snažili dostat počet znaků v řetězci větší.

80
00:03:24,630 --> 00:03:26,960
No, to by nebylo jedno, jak velký uděláte řetězec,

81
00:03:26,960 --> 00:03:28,690
dokonce milionů znaků,

82
00:03:28,690 --> 00:03:31,150
vše, co budu muset udělat, najít aktivní délku struny s tímto přístupem,

83
00:03:31,150 --> 00:03:33,790
je přečíst hodnotu proměnné len,

84
00:03:33,790 --> 00:03:35,440
které jste již provedena.

85
00:03:35,440 --> 00:03:38,200
Vstupní délka, to znamená, že délka řetězce, který se snažíte najít,

86
00:03:38,200 --> 00:03:41,510
nemá vliv vůbec, jak rychle váš program běží.

87
00:03:41,510 --> 00:03:44,550
Tato část programu by běžet stejně rychle na jeden řetězec znaků

88
00:03:44,550 --> 00:03:46,170
a tisíc znakový řetězec,

89
00:03:46,170 --> 00:03:49,140
a to je důvod, proč by tento program být odkazoval se na jako běh v konstantním čase

90
00:03:49,140 --> 00:03:51,520
s ohledem na vstupní velikost.

91
00:03:51,520 --> 00:03:53,920
>> Samozřejmě, je tu nevýhodu.

92
00:03:53,920 --> 00:03:55,710
Můžete strávit další paměť v počítači

93
00:03:55,710 --> 00:03:57,380
ukládání proměnné

94
00:03:57,380 --> 00:03:59,270
a více času to bude trvat

95
00:03:59,270 --> 00:04:01,490
dělat skutečné uložení proměnné,

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

97
00:04:03,390 --> 00:04:05,060
zjistit, jak dlouho bude řetězec byl

98
00:04:05,060 --> 00:04:07,600
nezávisí na délce řetězce vůbec.

99
00:04:07,600 --> 00:04:10,720
Takže, to běží v O (1), nebo konstantní čas.

100
00:04:10,720 --> 00:04:13,070
To rozhodně nemusí znamenat,

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

102
00:04:15,610 --> 00:04:17,470
ale bez ohledu na to, kolik kroků je to,

103
00:04:17,470 --> 00:04:20,019
pokud nemění s velikostí vstupů,

104
00:04:20,019 --> 00:04:23,420
je to stále asymptoticky konstanta, která se představuje jako O (1).

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

106
00:04:25,120 --> 00:04:27,940
existuje mnoho různých velkých O běhové měřit algoritmy s.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algoritmy jsou asymptoticky pomalejší než algoritmy O (n).

108
00:04:32,980 --> 00:04:35,910
To znamená, že jako počet prvků (n) roste,

109
00:04:35,910 --> 00:04:39,280
nakonec O (n) ² algoritmy budou mít více času

110
00:04:39,280 --> 00:04:41,000
než O (n) algoritmy pro spuštění.

111
00:04:41,000 --> 00:04:43,960
To neznamená, O (n) algoritmy vždy běžet rychleji

112
00:04:43,960 --> 00:04:46,410
než O (N) ² algoritmů, a to i ve stejném prostředí,

113
00:04:46,410 --> 00:04:48,080
na stejném hardwaru.

114
00:04:48,080 --> 00:04:50,180
Možná, že pro malé vstupní velikosti,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algoritmus ve skutečnosti může pracovat rychleji,

116
00:04:52,900 --> 00:04:55,450
ale, nakonec, jako vstupní velikosti 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
nakonec zastínit runtime O (n) algoritmu.

119
00:05:02,000 --> 00:05:04,230
Stejně jako nějaké kvadratické matematické funkce

120
00:05:04,230 --> 00:05:06,510
 nakonec předběhnou všechny lineární funkce,

121
00:05:06,510 --> 00:05:09,200
bez ohledu na to, kolik z hlavy kdo lineární funkci začíná s.

122
00:05:10,010 --> 00:05:12,000
Pokud pracujete s velkým množstvím dat,

123
00:05:12,000 --> 00:05:15,510
algoritmy, které pracují v O (n) ² doba se může opravdu skončit zpomalení programu,

124
00:05:15,510 --> 00:05:17,770
ale pro malé vstupní velikosti,

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

126
00:05:19,420 --> 00:05:21,280
>> Další asymptotická složitost je,

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

128
00:05:24,420 --> 00:05:26,340
Příkladem algoritmu, který běží tak rychle

129
00:05:26,340 --> 00:05:29,060
je klasický binární vyhledávací algoritmus,

130
00:05:29,060 --> 00:05:31,850
pro zjištění prvku v již tříděném seznamu prvků.

131
00:05:31,850 --> 00:05:33,400
>> Pokud nevíte, co binární vyhledávací dělá,

132
00:05:33,400 --> 00:05:35,170
Vysvětlím ti to pro tebe opravdu rychle.

133
00:05:35,170 --> 00:05:37,020
Řekněme, že hledáte pro čí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á se na střední prvku matice

136
00:05:42,140 --> 00:05:46,830
a ptá se: "Je element chci větší, rovna nebo menší než toto?"

137
00:05:46,830 --> 00:05:49,150
Pokud je to stejné, pak skvělé. Našli jste prvek, a máte hotovo.

138
00:05:49,150 --> 00:05:51,300
Pokud je to větší, pak víte, že prvek

139
00:05:51,300 --> 00:05:53,440
musí být v pravé části pole,

140
00:05:53,440 --> 00:05:55,200
a můžete se podívat na, že v budoucnu,

141
00:05:55,200 --> 00:05:57,690
a, pokud je to menší, pak víte, že má být na levé straně.

142
00:05:57,690 --> 00:06:00,980
Tento proces se opakuje s menší velikosti pole

143
00:06:00,980 --> 00:06:02,870
až do dosažení správné prvek nalezen.

144
00:06:08,080 --> 00:06:11,670
>> Tento výkonný algoritmus snižuje velikost pole na polovinu každé operaci.

145
00:06:11,670 --> 00:06:14,080
Takže, najít element v tříděném poli o velikosti 8,

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

147
00:06:16,170 --> 00:06:18,450
nebo 3 z těchto operací,

148
00:06:18,450 --> 00:06:22,260
kontrolu střední prvek, pak dělení pole na polovinu bude nutné,

149
00:06:22,260 --> 00:06:25,670
vzhledem k tomu, pole o velikosti 16 má (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
nebo 4 operace.

151
00:06:27,480 --> 00:06:30,570
To je pouze 1 více provoz na dvojnásobek velikosti pole.

152
00:06:30,570 --> 00:06:32,220
Zdvojnásobení velikosti pole

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

154
00:06:35,160 --> 00:06:37,770
Opět, kontrola prostřední prvek seznamu, pak rozdělení.

155
00:06:37,770 --> 00:06:40,440
Takže, je to údajně v provozu v logaritmickém čase,

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

157
00:06:42,440 --> 00:06:44,270
Ale počkejte, vy říkáte,

158
00:06:44,270 --> 00:06:47,510
není to závisí na tom, kde v seznamu prvek, který hledáte, je?

159
00:06:47,510 --> 00:06:50,090
Co když první prvek se podíváte na stane, že je správná?

160
00:06:50,090 --> 00:06:52,040
Pak, to trvá jen 1 operaci,

161
00:06:52,040 --> 00:06:54,310
bez ohledu na to, jak velký je seznam.

162
00:06:54,310 --> 00:06:56,310
>> No, to je důvod, proč počítačoví odborníci mají více pojmů

163
00:06:56,310 --> 00:06:58,770
pro asymptotické složitosti, které odrážejí nejlepší případ

164
00:06:58,770 --> 00:07:01,050
a nejhorší vystoupení algoritmu.

165
00:07:01,050 --> 00:07:03,320
Více správně, horní a dolní hranice

166
00:07:03,320 --> 00:07:05,090
na běhu.

167
00:07:05,090 --> 00:07:07,660
V nejlepším případě pro binární vyhledávání, náš prvek

168
00:07:07,660 --> 00:07:09,330
přímo tam uprostřed,

169
00:07:09,330 --> 00:07:11,770
a dostanete ho v konstantním čase,

170
00:07:11,770 --> 00:07:14,240
bez ohledu na to, jak velká zbytek pole je.

171
00:07:15,360 --> 00:07:17,650
Symbol použitý pro toto je Ω.

172
00:07:17,650 --> 00:07:19,930
Takže, je tento algoritmus říká běžet Ω (1).

173
00:07:19,930 --> 00:07:21,990
V nejlepším případě, že najde prvek rychle,

174
00:07:21,990 --> 00:07:24,200
bez ohledu na to, jak velký je pole,

175
00:07:24,200 --> 00:07:26,050
ale v nejhorším případě,

176
00:07:26,050 --> 00:07:28,690
má provést (log n) roztřepené kontroly

177
00:07:28,690 --> 00:07:31,030
z pole najít ten správný prvek.

178
00:07:31,030 --> 00:07:34,270
Nejhorší horní hranice jsou odkazoval se na s velkým "O", které už zná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ární vyhledávání, naopak,

181
00:07:40,680 --> 00:07:43,220
, ve kterém se projdete každý prvek pole

182
00:07:43,220 --> 00:07:45,170
najít ten, který chcete,

183
00:07:45,170 --> 00:07:47,420
je v nejlepším případě Ω (1).

184
00:07:47,420 --> 00:07:49,430
Opět, první prvek, který chcete.

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

186
00:07:51,930 --> 00:07:54,840
V nejhorším případě, je to poslední prvek v poli.

187
00:07:54,840 --> 00:07:58,560
Takže, budete muset projít všechny n prvků v poli najít,

188
00:07:58,560 --> 00:08:02,170
jako když hledali 3.

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

190
00:08:06,030 --> 00:08:09,330
, protože je to přímo úměrná počtu prvků v poli.

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

192
00:08:12,830 --> 00:08:15,820
To může být použit k popisu algoritmů, kde je nejlepší a nejhorší případy

193
00:08:15,820 --> 00:08:17,440
jsou stejné.

194
00:08:17,440 --> 00:08:20,390
To je případ string-length algoritmů jsme hovořili o dříve.

195
00:08:20,390 --> 00:08:22,780
To znamená, že pokud uložíme ji do proměnné před

196
00:08:22,780 --> 00:08:25,160
uložíme řetězec a přístup později v konstantním čase.

197
00:08:25,160 --> 00:08:27,920
Bez ohledu na to, jaký počet

198
00:08:27,920 --> 00:08:30,130
jsme skladování v této proměnné, budeme se muset podívat na to.

199
00:08:33,110 --> 00:08:35,110
Nejlepší věc je, že jsme se na to podívat

200
00:08:35,110 --> 00:08:37,120
a najít délku řetězce.

201
00:08:37,120 --> 00:08:39,799
Takže Ω (1) nebo best case konstantní čas.

202
00:08:39,799 --> 00:08:41,059
Nejhorší případ je,

203
00:08:41,059 --> 00:08:43,400
Podíváme se na to a najít délku řetězce.

204
00:08:43,400 --> 00:08:47,300
Takže, O (1), nebo konstantní čas v nejhorším případě.

205
00:08:47,300 --> 00:08:49,180
Takže, protože nejlepší věci a nejhorší případy jsou stejné,

206
00:08:49,180 --> 00:08:52,520
Tento lze říci, že běží v Θ (1), je čas.

207
00:08:54,550 --> 00:08:57,010
>> Stručně řečeno, máme dobré způsoby, jak uvažovat o účinnosti kódy

208
00:08:57,010 --> 00:09:00,110
aniž by věděl něco o real-světového času kdy přijmou běžet,

209
00:09:00,110 --> 00:09:02,270
která je ovlivněna spoustou vnějších faktorů,

210
00:09:02,270 --> 00:09:04,190
včetně odlišného hardwaru, softwaru,

211
00:09:04,190 --> 00:09:06,040
nebo specifika vašeho kódu.

212
00:09:06,040 --> 00:09:08,380
Také, to nám umožňuje rozum, dobře o tom, co se stane

213
00:09:08,380 --> 00:09:10,180
kdy velikost vstupů zvyšuje.

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

215
00:09:12,490 --> 00:09:15,240
nebo ještě hůře, O (2 ⁿ) algoritmus,

216
00:09:15,240 --> 00:09:17,170
jeden z nejrychleji rostoucích typů,

217
00:09:17,170 --> 00:09:19,140
budete opravdu začnete si uvědomovat, zpomalení

218
00:09:19,140 --> 00:09:21,220
když začnete pracovat s velkým množstvím dat.

219
00:09:21,220 --> 00:09:23,590
>> To je asymptotická složitost. Díky.